[Cake] small cake_hash optimization?

[Cake] small cake_hash optimization?

[Pete Heist]

I’ve been playing around with cake’s hashing and happened to notice in cake_hash that it seems like srchost_idx and dsthost_idx could rather be calculated only if need_allocate_src or need_allocate_dst are true, respectively, as the values are only used inside those code blocks.

I’ve not done any testing on what the real impact of this change would be, or even if it breaks something.

Forgive me for any waste of time if I’ve missed something here...

-----

sysadmin@apu2b:~/src/sch_cake$ git diff sch_cake.c
diff --git a/sch_cake.c b/sch_cake.c
index 97a27be..8f59917 100644
--- a/sch_cake.c
+++ b/sch_cake.c
@@ -747,8 +747,6 @@ cake_hash(struct cake_tin_data *q, const struct sk_buff *skb, int flow_mode)
        }
 
        reduced_hash = flow_hash    % CAKE_QUEUES;
-       srchost_idx  = srchost_hash % CAKE_QUEUES;
-       dsthost_idx  = dsthost_hash % CAKE_QUEUES;
 
        /* set-associative hashing */
        /* fast path if no hash collision (direct lookup succeeds) */
@@ -809,6 +807,7 @@ found:
                q->tags[reduced_hash] = flow_hash;
 
                if (need_allocate_src) {
+                       srchost_idx = srchost_hash % CAKE_QUEUES;
                        inner_hash = srchost_idx % CAKE_SET_WAYS;
                        outer_hash = srchost_idx - inner_hash;
                        for (i = 0, k = inner_hash; i < CAKE_SET_WAYS;
@@ -830,6 +829,7 @@ found_src:
                }
 
                if (need_allocate_dst) {
+                       dsthost_idx = dsthost_hash % CAKE_QUEUES;
                        inner_hash = dsthost_idx % CAKE_SET_WAYS;
                        outer_hash = dsthost_idx - inner_hash;
                        for (i = 0, k = inner_hash; i < CAKE_SET_WAYS;

-----

Re: [Cake] small cake_hash optimization?

[Pete Heist]

[-- Attachment #1: Type: text/plain, Size: 631 bytes --]


> On Nov 22, 2017, at 11:06 AM, Pete Heist <peteheist@gmail.com> wrote:
> 
> I’ve not done any testing on what the real impact of this change would be, or even if it breaks something.

Ok, at least a little crude testing with sar:

https://docs.google.com/spreadsheets/d/1LKoq5NaswuHm9H1atXoZA1AhNDg6L4UYS3Pn5lCsb1I/edit#gid=0 <https://docs.google.com/spreadsheets/d/1LKoq5NaswuHm9H1atXoZA1AhNDg6L4UYS3Pn5lCsb1I/edit#gid=0>

~10% less cake CPU at GigE in this case? What’s a better tool for timing kernel module functions?

Would really need to test if host fairness still works, otherwise this is irrelevant…


[-- Attachment #2: Type: text/html, Size: 1217 bytes --]

Re: [Cake] small cake_hash optimization?

[Sebastian Moeller]

Hi Pete,

[NITPICK]
please note that "cake 950mbit " will only assume 14 bytes overhead which does not reflect what is really happening on ethernet

Gb Ethernet:
7 Byte Preamble + 1 Byte start of frame delimiter (SFD) + 12 Byte inter frame gap (IFG) + 4 Byte Frame Check Sequence (FCS) + 6 (dest MAC) + 6 (src MAC) + 2 (ethertype)
7 + 1 + 12 + 4 + 6 + 6 + 2 = 38 bytes

so the actual consumed bandwidth for MTU 1500 packets will be:

950 * ((1538)/(1514)) = 965.06 Mbps

so below a MTU of (14 * (1000/950) - 38) / (1 - (1000/950)) = 442 Byte the cake shaper will not avoid filling the ethernet NIC's queues (which might not be a bid issue with BQL).


I guess my point is when shaping ethernet be sure to add "overhead 64 mpu 84" to your cake invocation to actually account for the link layer properties.
[/NITPICK]

Best Regards


> On Nov 22, 2017, at 13:37, Pete Heist <peteheist@gmail.com> wrote:
> 
> 
>> On Nov 22, 2017, at 11:06 AM, Pete Heist <peteheist@gmail.com> wrote:
>> 
>> I’ve not done any testing on what the real impact of this change would be, or even if it breaks something.
> 
> Ok, at least a little crude testing with sar:
> 
> https://docs.google.com/spreadsheets/d/1LKoq5NaswuHm9H1atXoZA1AhNDg6L4UYS3Pn5lCsb1I/edit#gid=0
> 
> ~10% less cake CPU at GigE in this case? What’s a better tool for timing kernel module functions?
> 
> Would really need to test if host fairness still works, otherwise this is irrelevant…
> 
> _______________________________________________
> Cake mailing list
> Cake@lists.bufferbloat.net
> https://lists.bufferbloat.net/listinfo/cake

Re: [Cake] small cake_hash optimization?

[Dave Taht]

On Wed, Nov 22, 2017 at 4:37 AM, Pete Heist <peteheist@gmail.com> wrote:
>
> On Nov 22, 2017, at 11:06 AM, Pete Heist <peteheist@gmail.com> wrote:
>
> I’ve not done any testing on what the real impact of this change would be,
> or even if it breaks something.
>
>
> Ok, at least a little crude testing with sar:
>
> https://docs.google.com/spreadsheets/d/1LKoq5NaswuHm9H1atXoZA1AhNDg6L4UYS3Pn5lCsb1I/edit#gid=0
>
> ~10% less cake CPU at GigE in this case?

Divides do hurt, particularly if you can't do them out of order. But
that seems like a lot.

> What’s a better tool for timing
> kernel module functions?

Use "perf"

https://en.wikipedia.org/wiki/Perf_(Linux)

>
> Would really need to test if host fairness still works, otherwise this is
> irrelevant…
>
>
> _______________________________________________
> Cake mailing list
> Cake@lists.bufferbloat.net
> https://lists.bufferbloat.net/listinfo/cake
>



-- 

Dave Täht
CEO, TekLibre, LLC
http://www.teklibre.com
Tel: 1-669-226-2619

Re: [Cake] small cake_hash optimization?

[Pete Heist]

> On Nov 22, 2017, at 7:33 PM, Dave Taht <dave.taht@gmail.com> wrote:
> 
> On Wed, Nov 22, 2017 at 4:37 AM, Pete Heist <peteheist@gmail.com> wrote:
>> 
>> Ok, at least a little crude testing with sar:
>> 
>> https://docs.google.com/spreadsheets/d/1LKoq5NaswuHm9H1atXoZA1AhNDg6L4UYS3Pn5lCsb1I/edit#gid=0
>> 
>> ~10% less cake CPU at GigE in this case?
> 
> Divides do hurt, particularly if you can't do them out of order. But
> that seems like a lot.

Hrm, I tried a second test to make sure fairness still works (it does) but this time got a slight _negative_ result (rrul_be fair tab). So this calls into question whether or not my testing method is very good, and also whether or not the change actually helps much.

This time I used "cake unlimited besteffort dual-srchost overhead 64 mpu 84” (overheads from Sebastian, just rely on bql).

I might try again with 950mbit limiting, and ‘perf’ instead.

Also I noted that the ‘lan’ keyword seemed to adversely affect host fairness, so I stopped using it. I’ll address that separately when there’s time.

>> What’s a better tool for timing
>> kernel module functions?
> 
> Use "perf"
> 
> https://en.wikipedia.org/wiki/Perf_(Linux)

Ok, will see if I can give it a try.

Re: [Cake] small cake_hash optimization?

[Sebastian Moeller]

Hi Pete,

> On Nov 22, 2017, at 19:43, Pete Heist <peteheist@gmail.com> wrote:
> 
> 
>> On Nov 22, 2017, at 7:33 PM, Dave Taht <dave.taht@gmail.com> wrote:
>> 
>> On Wed, Nov 22, 2017 at 4:37 AM, Pete Heist <peteheist@gmail.com> wrote:
>>> 
>>> Ok, at least a little crude testing with sar:
>>> 
>>> https://docs.google.com/spreadsheets/d/1LKoq5NaswuHm9H1atXoZA1AhNDg6L4UYS3Pn5lCsb1I/edit#gid=0
>>> 
>>> ~10% less cake CPU at GigE in this case?
>> 
>> Divides do hurt, particularly if you can't do them out of order. But
>> that seems like a lot.
> 
> Hrm, I tried a second test to make sure fairness still works (it does) but this time got a slight _negative_ result (rrul_be fair tab). So this calls into question whether or not my testing method is very good, and also whether or not the change actually helps much.
> 
> This time I used "cake unlimited besteffort dual-srchost overhead 64 mpu 84” (overheads from Sebastian, just rely on bql).

	I should have mentioned "overhead 64 mpu 84" only make sense in combination with a shaper limit (well, they will make sure the cake statistics will be more reflective of what is happening on the ethernet wire, but I am not sure whether that is worth the run-time cost the overhead calculation incurs).

Somewhat unrelated, I wondered about all the excitement about irtt and cloned the repository to my mac, and was absolutely delighted to realize that irtt will also effortlessly work under macos. I only have run the demo from the readme.md with both client and server running at the same machine, but I got results that look reasonable on first sight (but I admit I really do not know exact;y what to expect). This is really great!


Best Regards


> 
> I might try again with 950mbit limiting, and ‘perf’ instead.
> 
> Also I noted that the ‘lan’ keyword seemed to adversely affect host fairness, so I stopped using it. I’ll address that separately when there’s time.
> 
>>> What’s a better tool for timing
>>> kernel module functions?
>> 
>> Use "perf"
>> 
>> https://en.wikipedia.org/wiki/Perf_(Linux)
> 
> Ok, will see if I can give it a try.
> _______________________________________________
> Cake mailing list
> Cake@lists.bufferbloat.net
> https://lists.bufferbloat.net/listinfo/cake

Re: [Cake] small cake_hash optimization?

[Pete Heist]

[-- Attachment #1: Type: text/plain, Size: 1653 bytes --]


> On Nov 23, 2017, at 9:00 AM, Sebastian Moeller <moeller0@gmx.de> wrote:
> 
> Hi Pete,
> 
> 	I should have mentioned "overhead 64 mpu 84" only make sense in combination with a shaper limit (well, they will make sure the cake statistics will be more reflective of what is happening on the ethernet wire, but I am not sure whether that is worth the run-time cost the overhead calculation incurs).
> 
> Somewhat unrelated, I wondered about all the excitement about irtt and cloned the repository to my mac, and was absolutely delighted to realize that irtt will also effortlessly work under macos. I only have run the demo from the readme.md with both client and server running at the same machine, but I got results that look reasonable on first sight (but I admit I really do not know exact;y what to expect). This is really great!

Thanks for the overhead info. I used that in my latest tests. That makes me wonder if those overheads could be defaulted when Cake knows Ethernet is being used with rate limiting? I know a goal is to make cake easier to configure so such things are examples of what people are likely to miss.

Glad to hear irtt runs for you! I was waiting to post something until I clean up some more things in the todo list, but since you found it, let me know (file an Issue) if you find any problems. Also, if you have something later than El Capitan, I might be interested to see the output from “irtt sleep” or ten seconds or so from “irtt clock”, as I’m gradually learning about timer/clock behavior on different OSs. I guess it could also be filed as an Issue, so we don’t add too much to the cake list...

[-- Attachment #2: Type: text/html, Size: 5109 bytes --]

Re: [Cake] small cake_hash optimization?

[Pete Heist]

> On Nov 23, 2017, at 10:30 AM, Pete Heist <peteheist@gmail.com> wrote:
> 
> Thanks for the overhead info. I used that in my latest tests. That makes me wonder if those overheads could be defaulted when Cake knows Ethernet is being used with rate limiting? I know a goal is to make cake easier to configure so such things are examples of what people are likely to miss.

BTW I realize there’s no way cake can know what the overheads should actually be, just to make sure the defaults are sensible I guess. I know overheads are not an easy thing.

Re: [Cake] small cake_hash optimization?

[Dave Taht]

On Thu, Nov 23, 2017 at 1:36 AM, Pete Heist <peteheist@gmail.com> wrote:
>
>> On Nov 23, 2017, at 10:30 AM, Pete Heist <peteheist@gmail.com> wrote:
>>
>> Thanks for the overhead info. I used that in my latest tests. That makes me wonder if those overheads could be defaulted when Cake knows Ethernet is being used with rate limiting? I know a goal is to make cake easier to configure so such things are examples of what people are likely to miss.
>
> BTW I realize there’s no way cake can know what the overheads should actually be, just to make sure the defaults are sensible I guess. I know overheads are not an easy thing.

I note that the man page needs love.

> _______________________________________________
> Cake mailing list
> Cake@lists.bufferbloat.net
> https://lists.bufferbloat.net/listinfo/cake



-- 

Dave Täht
CEO, TekLibre, LLC
http://www.teklibre.com
Tel: 1-669-226-2619

Re: [Cake] small cake_hash optimization?

[Sebastian Moeller]

> On Nov 23, 2017, at 17:21, Dave Taht <dave.taht@gmail.com> wrote:
> 
> On Thu, Nov 23, 2017 at 1:36 AM, Pete Heist <peteheist@gmail.com> wrote:
>> 
>>> On Nov 23, 2017, at 10:30 AM, Pete Heist <peteheist@gmail.com> wrote:
>>> 
>>> Thanks for the overhead info. I used that in my latest tests. That makes me wonder if those overheads could be defaulted when Cake knows Ethernet is being used with rate limiting? I know a goal is to make cake easier to configure so such things are examples of what people are likely to miss.
>> 
>> BTW I realize there’s no way cake can know what the overheads should actually be, just to make sure the defaults are sensible I guess. I know overheads are not an easy thing.
> 
> I note that the man page needs love.

	Is there a decent editor for man pages (preferably WYSIWYG?) or a simple template to fil out, or is the structure fine and you want fine combing through the content and leaving the structure as is?

Best Regards


> 
>> _______________________________________________
>> Cake mailing list
>> Cake@lists.bufferbloat.net
>> https://lists.bufferbloat.net/listinfo/cake
> 
> 
> 
> -- 
> 
> Dave Täht
> CEO, TekLibre, LLC
> http://www.teklibre.com
> Tel: 1-669-226-2619

Re: [Cake] small cake_hash optimization?

[Dave Taht]

Sebastian Moeller <moeller0@gmx.de> writes:

>> On Nov 23, 2017, at 17:21, Dave Taht <dave.taht@gmail.com> wrote:
>> 
>> On Thu, Nov 23, 2017 at 1:36 AM, Pete Heist <peteheist@gmail.com> wrote:
>>> 
>>>> On Nov 23, 2017, at 10:30 AM, Pete Heist <peteheist@gmail.com> wrote:
>>>> 
>>>> Thanks for the overhead info. I used that in my latest tests. That makes me
>>>> wonder if those overheads could be defaulted when Cake knows Ethernet is
>>>> being used with rate limiting? I know a goal is to make cake easier to
>>>> configure so such things are examples of what people are likely to miss.
>>> 
>>> BTW I realize there’s no way cake can know what the overheads should actually be, just to make sure the defaults are sensible I guess. I know overheads are not an easy thing.
>> 
>> I note that the man page needs love.
>
> 	Is there a decent editor for man pages (preferably WYSIWYG?) or a simple template to fil out, or is the structure fine and you want fine combing through the content and leaving the structure as is?

Not really. Welcome to the 70s. Emacs?

The structure of the man page is fine

ack-filter no-ack-filter
wash

are missing

the example tc -s output is out of date and should be a capture during
some actual usage

addl author credits

> Best Regards
>
>
>> 
>>> _______________________________________________
>>> Cake mailing list
>>> Cake@lists.bufferbloat.net
>>> https://lists.bufferbloat.net/listinfo/cake
>> 
>> 
>> 
>> -- 
>> 
>> Dave Täht
>> CEO, TekLibre, LLC
>> http://www.teklibre.com
>> Tel: 1-669-226-2619
>
> _______________________________________________
> Cake mailing list
> Cake@lists.bufferbloat.net
> https://lists.bufferbloat.net/listinfo/cake

Re: [Cake] small cake_hash optimization?

[Sebastian Moeller]

Hi Pete,

> On Nov 23, 2017, at 10:30, Pete Heist <peteheist@gmail.com> wrote:
> 
> 
>> On Nov 23, 2017, at 9:00 AM, Sebastian Moeller <moeller0@gmx.de> wrote:
>> 
>> Hi Pete,
>> 
>> 	I should have mentioned "overhead 64 mpu 84" only make sense in combination with a shaper limit (well, they will make sure the cake statistics will be more reflective of what is happening on the ethernet wire, but I am not sure whether that is worth the run-time cost the overhead calculation incurs).
>> 
>> Somewhat unrelated, I wondered about all the excitement about irtt and cloned the repository to my mac, and was absolutely delighted to realize that irtt will also effortlessly work under macos. I only have run the demo from the readme.md with both client and server running at the same machine, but I got results that look reasonable on first sight (but I admit I really do not know exact;y what to expect). This is really great!
> 
> Thanks for the overhead info. I used that in my latest tests. That makes me wonder if those overheads could be defaulted when Cake knows Ethernet is being used with rate limiting? I know a goal is to make cake easier to configure so such things are examples of what people are likely to miss.

	Well, as you note later cake really has no idea what the user wants unless the user actually explicitly requests it. But in your case, I believe instead of the explicit "overhead 38 mpu 84" (I note the 64 above is a typo) you could use the "ethernet" keyword which will under the hood expand to the same values. Personally I am not a big friend of the keywords, but even I admit that they help users lacking the time to dive into the details, especially if the name is as obvious as "ethernet" (all I would wish though would be that these keywords wouls still need to be lead by the "overhead" command, so "overhead ethernet" instead of "ethernet", because that IMHO would be more explicit, but I digress).
Please note that I currently have issues with overhead accounting with on dave's cobalt branch and the new iproute2 tools, automatic kernel overhead accounting does not seem to work at all, so could you please post the output of:
tc -s qdisc
after one of your experiments to confirm that the requested overhead was actually applied?


> 
> Glad to hear irtt runs for you! I was waiting to post something until I clean up some more things in the todo list, but since you found it, let me know (file an Issue) if you find any problems. Also, if you have something later than El Capitan, I might be interested to see the output from “irtt sleep” or ten seconds or so from “irtt clock”, as I’m gradually learning about timer/clock behavior on different OSs. I guess it could also be filed as an Issue, so we don’t add too much to the cake list...

As I am currently on 10.12.6 Sierra, I just went and created two new issues with the requested information; I should note this is a pre-fancy-oled-replacement-for-function-keys macbook pro with a quad 2.5 GHz i7 cpu.

Best Regards
	Sebastian

Re: [Cake] small cake_hash optimization?

[Dave Taht]

It is somewhat unfair to not include the pfifo bandwidth on the test
(a cpu cost/byte might be a better metric), also pfifo_fast has three
tiers of classification in it.

Re: [Cake] small cake_hash optimization?

[Pete Heist]

> On Nov 22, 2017, at 7:38 PM, Dave Taht <dave.taht@gmail.com> wrote:
> 
> It is somewhat unfair to not include the pfifo bandwidth on the test
> (a cpu cost/byte might be a better metric), also pfifo_fast has three
> tiers of classification in it.

Yeah, it’s probably better to not try to subtract the pfifo_fast system time out in the way that I did. I should probably just compare cake with and without the change, using a more accurate tool.

I don’t see how the change could hurt, but I also now am not sure it helps much either. I guess it’s just two divs per call to cake_hash, which is obviously going to happen more at GigE.

Thanks for the advice…

Re: [Cake] small cake_hash optimization?

[Pete Heist]

[-- Attachment #1: Type: text/plain, Size: 1606 bytes --]


> On Nov 22, 2017, at 7:49 PM, Pete Heist <peteheist@gmail.com> wrote:
> 
>> On Nov 22, 2017, at 7:38 PM, Dave Taht <dave.taht@gmail.com> wrote:
>> 
>> It is somewhat unfair to not include the pfifo bandwidth on the test
>> (a cpu cost/byte might be a better metric), also pfifo_fast has three
>> tiers of classification in it.
> 
> Yeah, it’s probably better to not try to subtract the pfifo_fast system time out in the way that I did. I should probably just compare cake with and without the change, using a more accurate tool.
> 
> I don’t see how the change could hurt, but I also now am not sure it helps much either. I guess it’s just two divs per call to cake_hash, which is obviously going to happen more at GigE.


I didn’t figure out ‘perf’ for this, but I did instrument cake_hash in a simple way with calls to local_clock_ns using ‘stap'. Results on stap tab:

https://docs.google.com/spreadsheets/d/1LKoq5NaswuHm9H1atXoZA1AhNDg6L4UYS3Pn5lCsb1I/edit#gid=1493356365 <https://docs.google.com/spreadsheets/d/1LKoq5NaswuHm9H1atXoZA1AhNDg6L4UYS3Pn5lCsb1I/edit#gid=1493356365>

It’s a head scratcher, but I saw about a 3% mean time reduction in cake_hash for the “optimized” version when limited at 950mbit, and a very slight slowdown when unlimited. “Confounding”...(by Estee Lauder).

Whether or not those results are either correct or statistically significant, it doesn’t look like it’s worth too much more effort, and I can leave it to you whether you want this change or not. I don’t see the harm in it, and neither do I see much of a benefit.

[-- Attachment #2: Type: text/html, Size: 2400 bytes --]

Re: [Cake] small cake_hash optimization?

[Dave Taht]

I'll take it. I did a commit with your Suggested-by: pull it.