tasklwIP - A Lightweight TCP/IP stack - Tasks: task #6827, etharp could need some tuning

 
 

You are not allowed to post comments on this tracker with your current authentication level.

task #6827: etharp could need some tuning

Submitted by:  Simon Goldschmidt <goldsimon>
Submitted on:  Fri 27 Apr 2007 11:50:15 AM UTC  
 
Category:  ARP Should Start On:  Wed 27 Jun 2007 12:00:00 AM UTC
Should be Finished on:  Fri 27 Apr 2007 12:00:00 AM UTC Priority:  3 - Low
Status:  Done Privacy:  Public
Percent Complete:  100% Assigned to:  Simon Goldschmidt <goldsimon>
Open/Closed:  Closed Planned Release:  None
Effort:  10.00

( Jump to the original submission)

Tue 03 Jul 2007 08:10:21 AM UTC, comment #55: 

Because I forgot that. I've just added it.

Simon Goldschmidt <goldsimon>
Project AdministratorIn charge of this item.
Tue 03 Jul 2007 07:27:53 AM UTC, comment #54: 

Why the addr_hint field of IP_PCB in ip.h is not between a #if LWIP_NETIF_HWADDRHINT/#endif ?

Frédéric Bernon <fbernon>
Project Member
Mon 02 Jul 2007 08:42:47 PM UTC, comment #53: 

I've checked in the patch for caching arp entries at pcb level, routed through the struct netif (default=off).

With this included, I think this task is finished.

Simon Goldschmidt <goldsimon>
Project AdministratorIn charge of this item.
Sat 30 Jun 2007 11:44:36 AM UTC, comment #52: 

Yep, good idea, done that.

Simon Goldschmidt <goldsimon>
Project AdministratorIn charge of this item.
Fri 29 Jun 2007 04:50:54 PM UTC, comment #51: 

Suggestion: Since you're "tuning" etharp, I would like to suggest the following minor change, which results in a savings of about 60 bytes of code on my ARM platform. Basically, setting the HWLEN & PROTOLEN in one statement rather than two.

(file #13198)

Jared Grubb <jgrubb>
Project Member
Tue 26 Jun 2007 07:51:02 AM UTC, comment #50: 

> I wonder how much the extra calls to ip_route will affect your performance.


I'd guess they won't! The old way was to call ip_output which then calls ip_route and ip_output_if. If ip_route is called from tcp_output directly, that doesn't change. You can say I'm moving the ip_output functionality into tcp_output. The only effect is the code gets a little bigger (but really only a little!). Regarding performance, one function call is saved, so it could indeed be faster...

Simon Goldschmidt <goldsimon>
Project AdministratorIn charge of this item.
Tue 26 Jun 2007 07:47:07 AM UTC, comment #49: 

I wonder how much the extra calls to ip_route will affect your performance.

Kieran Mansley <kieranm>
Project Member
Mon 25 Jun 2007 05:36:44 PM UTC, comment #48: 

Any comments to #42 (supplying the addr_hint pointer through the struct netif) from anyone? :)

Simon Goldschmidt <goldsimon>
Project AdministratorIn charge of this item.
Mon 25 Jun 2007 01:00:07 PM UTC, comment #47: 

Less code definitely wins even if there's a slight slow down, which I doubt will be a huge problem in this case.

Kieran Mansley <kieranm>
Project Member
Sun 24 Jun 2007 01:55:25 PM UTC, comment #46: 

Here's the right version:

(file #13146)

Simon Goldschmidt <goldsimon>
Project AdministratorIn charge of this item.
Sun 24 Jun 2007 01:53:04 PM UTC, comment #45: 

D'oh! Sent the wrong patch before, I've deleted it ;-)

Simon Goldschmidt <goldsimon>
Project AdministratorIn charge of this item.
Sun 24 Jun 2007 01:46:26 PM UTC, comment #44: 

I've created a patch that introduces a function 'etharp_send' that fills in the ethernet header (MAC addresses an type).

This static function is then called from all functions that previously called netif->linkoutput so that the generation of the ethernet header is only coded once (to reduce code size).

If this reduces code size, it might be slower. Some compilers could be so clever to inline the function with speed optimizations turned on. We still gain less C code then.

Please comment if you fear slowing down, or else I'll check it in some time!

(file #13145)

Simon Goldschmidt <goldsimon>
Project AdministratorIn charge of this item.
Sun 24 Jun 2007 01:13:51 PM UTC, comment #43: 

Shouldn't we re-send an ARP query in etharp_tmr for pending ARP entries. I can't find any information about that in RFC 826.

If we don't re-send, we don't have to queue packets in etharp_query() if etharp_request() fails.

Simon Goldschmidt <goldsimon>
Project AdministratorIn charge of this item.
Sun 24 Jun 2007 12:01:55 PM UTC, comment #42: 

> I quite like your solution conceptually, but agree it does
> involve some layering violations and lots of little
> modifications to the code, so not easily disabled with #define.


I've modified the 'addr_hint' solution by including an 'u8_t* add_hint' in struct netif. tcp/udp & raw set that pointer to their '&(pcb->addr_hint)' and reset it to NULL after calling ip_output_if.

That way, it can easily be defined out.

I'll attach a patch.

(Note: tcp needs to call ip_route & ip_output_if instead of ip_output to have the netif; because of that, IP_STATS_INC(ip.rterr) and snmp_inc_ipoutnoroutes() have to be moved from ip_output to ip_route).

(file #13144)

Simon Goldschmidt <goldsimon>
Project AdministratorIn charge of this item.
Fri 22 Jun 2007 01:28:57 PM UTC, comment #41: 

I quite like your solution conceptually, but agree it does involve some layering violations and lots of little modifications to the code, so not easily disabled with #define.

The sorted list is cleaner, but has some bad use cases where you spend more time sorting than you would searching.  Perhaps that's OK though.

I suppose in an ideal world we would just maintain this address hint feature as an optional extra (as a patch) and those that are interested would apply it, and those that weren't would stick with the current situation.  However, maintaining patches isn't much fun (at least with CVS - with something like mercurial it becomes much easier).

Kieran Mansley <kieranm>
Project Member
Thu 21 Jun 2007 08:15:48 PM UTC, comment #40: 

OK, so Frédéric is against passing the address hint. I'd like to have some more feedback, though! I don't want to include that option if it's only me who wants it!

I'm still looking for a way to use my address hint that can easily be disabled by a define.

I also like the sorted list, but it doesn't give me 'zero-searching' like the address hint would...

Simon Goldschmidt <goldsimon>
Project AdministratorIn charge of this item.
Tue 19 Jun 2007 04:33:20 PM UTC, comment #39: 

It would be equivalent to:
 for (k=6;k>0;k--)
and (unless the compiler optimises it by itself, which it might), that is typically faster than:
for (k = 0; k < 6; k++) {

because it tends to be faster on processors to compare against 0, than against a given constant. A constant adds to register pressure and has to be maintained in a register, or saved/restored in memory at the end of each loop for the check. Comparison against 0 can usually be done directly in a single instruction (or if using CISC where both would be single instruction, it would take fewer cycles).

Making your loops have a comparison against 0 does count as one of the more obscure optimisations you can do though, I agree.

Jonathan Larmour <jifl>
Project Member
Tue 19 Jun 2007 04:25:09 PM UTC, comment #38: 

OK, checked it in.

One question: etharp currently uses code like this to copy ethernet addresses:

k = 6;
while(k > 0) {
 k--;
 ...;
}

Is that faster than

for (k = 0; k < 6; k++) {
 ...;
}

or why is it that way? I didn't change it since the difference was not measurable on my embedded target...

Simon Goldschmidt <goldsimon>
Project AdministratorIn charge of this item.
Mon 18 Jun 2007 09:04:39 PM UTC, comment #37: 

Ok for me...

Frédéric Bernon <fbernon>
Project Member
Mon 18 Jun 2007 07:35:49 PM UTC, comment #36: 

Re comment #33/#34:

I'll do it, then. (of course with a define!)

Simon Goldschmidt <goldsimon>
Project AdministratorIn charge of this item.
Mon 18 Jun 2007 07:11:17 PM UTC, comment #35: 

>Perhaps in https://savannah.nongnu.org/task/?1551 ?


I thought about that, too. But first, this define would speed up the current code and it is not clear whether we get other physical layers for ARP any time. Second, in that task we also discussed making one core ARP file and another one for each physical layer (if the core file can contain enough code, anyway). So we can decide then whether we switch back to netif->hwaddrlen or have a define in each physical layer file...

In any case, I don't think that's gonna happen soon...

Simon Goldschmidt <goldsimon>
Project AdministratorIn charge of this item.
Sun 17 Jun 2007 03:57:56 PM UTC, comment #34: 

I don't see any objection about that (except, of course, use a define and not directly 6)...

Perhaps one thing: is there someone who told in a previous mail than ARP could be used for other physical layers than Ethernet?

Perhaps in https://savannah.nongnu.org/task/?1551 ?

Frédéric Bernon <fbernon>
Project Member
Sat 16 Jun 2007 12:05:37 PM UTC, comment #33: 

Since struct eth_addr->addr is always 6 bytes long, it doesn't make sense to always fetch netif->hwaddrlen.

I would always copy 6 bytes (the file is called etharp.c after all) and add an assert that netif->hwaddrlen is set to 6.

Any objections?

Simon Goldschmidt <goldsimon>
Project AdministratorIn charge of this item.
Fri 08 Jun 2007 11:02:18 PM UTC, comment #32: 

Checked in & updated all ports that called etharp_output() in their netif->output() function to set etharp_output() as their netif->output.

Hope all ports compile cleanly since I can't test most of them :-(

Simon Goldschmidt <goldsimon>
Project AdministratorIn charge of this item.
Fri 08 Jun 2007 10:10:28 PM UTC, comment #31: 

OK I'm not changing the 'cache' for now, but I'll check in the change of the order of parameters for etharp_output() to meet that of netif->output() so etharp_output() can be used directly as netif->output() to save a function call.

I'll also try to update all contrib modules.

Simon Goldschmidt <goldsimon>
Project AdministratorIn charge of this item.
Fri 08 Jun 2007 05:37:33 PM UTC, comment #30: 

Put "in head" the last entry used is not a real sort (2 pointers to change), and should be faster than pass an address inside all the stack. If you want an ARP cache with 20 entries, an send to 5 dest,  with a such feature, you never compare more than the 5 first entries. But I will read all others comments to have a better point of view...

Frédéric Bernon <fbernon>
Project Member
Fri 08 Jun 2007 05:20:21 PM UTC, comment #29: 

> To come back on the problem (and not on the proposed solution),
> isn't it better to replace in a first time the table by a
> single-link list?


This solution was already proposed (with the modification of putting a found entry one step forward instead of at the beginning to have an 'automatically sorted' list).

But in your situation, you would end up re-sorting the list every time. May be faster or slower than passing around address hints, I don't know! (And it depends on the hardware, I guess!)

Simon Goldschmidt <goldsimon>
Project AdministratorIn charge of this item.
Fri 08 Jun 2007 05:08:38 PM UTC, comment #28: 

To come back on the problem (and not on the proposed solution), isn't it better to replace in a first time the table by a single-link list? In current code, we store the "last" entry used in a variable. If we used a list, why don't simply "re-chain" the last to be in head? Like this, most used entries will got a fast access. Perhaps this solution was already proposed, but I don't have the time (now) to re-read all the comments...

Frédéric Bernon <fbernon>
Project Member
Fri 08 Jun 2007 04:45:30 PM UTC, comment #27: 

Although I don't have anything against introducing an option for this (an I've already thought about that), creating an option for one parameter to be left out is tricky and leads to code that is bad to read, I think.

Creating a define like
#define LINKLAYER_ADDR_HINT , u8_t *addr_hint
would be a solution for the optional parameters, but is it OK to include such a define in the code???

Still, what we would gain having an option without leaving away the parameter (and thus passing NULL around), would be 1 byte less in the pcbs and leaving out the pointer check in etharp.c:find_entry().

The problem with your UDP streams is that no caching algorithm (even hashing) can really avoid searching for the right entry, which is what the patch should do. So leaving it the way it is would be best for the situation you described?

Simon Goldschmidt <goldsimon>
Project AdministratorIn charge of this item.
Fri 08 Jun 2007 04:35:13 PM UTC, comment #26: 

About comment #23, "So very fast for TCP while slow for UDP if many different sendto destination are used, which should be rare.". Problem, it's wrong in my case, and I suppose in all application using realtime streams like video and audio (audiovideo servers, etc...).

I don't have study it in details, so, can you wait before check in? Or perhaps propose an option for that?

Frédéric Bernon <fbernon>
Project Member
Fri 08 Jun 2007 12:11:02 PM UTC, comment #25: 

I haven't look in detail, but I'm OK with the concept, and assuming you've done your best to minimise the impact on the rest of the stack, it should be fine.

Others might disagree of course!

Kieran Mansley <kieranm>
Project Member
Fri 08 Jun 2007 12:04:43 PM UTC, comment #24: 

Any comments on the patch to pass around an address hint?

I'd imagine some could think it's too much effort to pass additional arguments around the stack (size vs. speed?).

But since this is (at least in my opinion) the only solution to prevent searching the arp table too often, I'd like to check this in if noone objects.

Awaiting your comments ;-)

Simon Goldschmidt <goldsimon>
Project AdministratorIn charge of this item.
Tue 05 Jun 2007 02:46:20 PM UTC, comment #23: 

I've decided to use an u8_t pointer in this patch, which is included in IP_PCB and passed around from the IP protocols down to etharp (including netif->output() :( )

This patch should allow the etharp module to directly find a MAC address and only having to search if the remote address of a pcb changes. (So very fast for TCP while slow for UDP if many different sendto destination are used, which should be rare.)

(file #12960)

Simon Goldschmidt <goldsimon>
Project AdministratorIn charge of this item.
Fri 01 Jun 2007 07:50:26 AM UTC, comment #22: 

To minimize breaking the abstraction, we could add a pointer (u8_t pointer or to be more general, a void** which would mean having a void* member in the pcbs) 'addr_hint' that can be filled by the netif->output() or etharp_output() function, or whatever is behind netif->output(). 'addr_hint' would have to be passed through the IP layer and the netif down to the arp layer which could fill it. Protocols not needing this (e.g. icmp) would simply pass a null pointer.

Another thing to 'tune': etharp_output() has the same parameters as netif->output(), only in another order. If we make it the same order, ethernetif_init can directly set netif->output() to etharp_output() to save a function call.

Simon Goldschmidt <goldsimon>
Project AdministratorIn charge of this item.
Thu 31 May 2007 08:02:41 AM UTC, comment #21: 

Cunning.  Breaks the layered abstraction a bit (makes etharp dependent on the IP layer's state) but worthy of investigation.

Kieran Mansley <kieranm>
Project Member
Thu 31 May 2007 05:20:24 AM UTC, comment #20: 

I've just come up with an even better idea to tune the speed of etharp_output: We could store the last used arp_table index in every ip_pcb. Thus, if every ip_pcb knows its last used index, every TCP-connection should have to look only once which index it has to use, and for RAW and UDP pcbs, it should also significantly reduce the number of array-searches.

This would move the one-entry-cache from etharp into a one-entry-cache for every single connection. And since it is an integer only, it's performance gain at very low RAM usage.

The only question is how to neatly integrate it into the netif->output -> etharp_output calling chain. Maybe we can pass on the ip_pcb in addition to the ipaddr? Since it has to do with IP anyway, it wouldn't be that far away from what we are doing now (passing the ipaddr, I mean). And we could still allow a NULL-pointer so that nothing is done. If != NULL, etharp_output could update the index every time.

Simon Goldschmidt <goldsimon>
Project AdministratorIn charge of this item.
Wed 30 May 2007 01:55:32 PM UTC, comment #19: 

About comment #8, sorry, I forgot "not": you would say " should not have a high cost."

So, about comment #12, agree for the pointer, and for the list (if it's an option).

About comment #16: like Jonathan, I'm not so afraid about options (even if I can understand that too many options can make difficult to tune the stack). But one other interesting thing he said is "Am I atypical? Are people really usually communicating simultaneously with many hosts on the same subnet? ". I think that people use lwIP on very different targets and on very different uses. It will be great to organize a poll to study how users use lwIP. For the "lw" side? For the open source side (free, active communauty, port available...)? Because there is lot of features, compare to stacks like µIP? It will be good to know all that...

Frédéric Bernon <fbernon>
Project Member
Wed 30 May 2007 12:18:54 PM UTC, comment #18: 

I agree. I was commenting primarily because if it /wasn't/ going to be an option, I wasn't certain what (including the current implementation) would be the best one to retain.

Jonathan Larmour <jifl>
Project Member
Wed 30 May 2007 12:08:14 PM UTC, comment #17: 

>I find that ARP tables are usually only using a very small number of entries. Even swapping them may be unnecessary for the average number of entries. Am I atypical? Are people really usually communicating simultaneously with many hosts on the same subnet?


As long as I know (please correct me if I'm wrong), to be standard-conformant, you must include every ARP broadcast in your ARP table. That way, (or any other way, too) you can end up with the most used entry at the end of the array. That's why I wanted to include cache or swapping. The single-entry-cache works for one simultaneous communication and maybe that is enough for lwIP.

I think we can make it a (well documented) option to switch the entries and be done. If someone has simultaneous connections, they can switch the entries, the rest can live with the single-entry-cache. OK? (That way we even don't need the pointer-return-value for find_entry()).

Simon Goldschmidt <goldsimon>
Project AdministratorIn charge of this item.
Wed 30 May 2007 11:47:46 AM UTC, comment #16: 

I find that ARP tables are usually only using a very small number of entries. Even swapping them may be unnecessary for the average number of entries. Am I atypical? Are people really usually communicating simultaneously with many hosts on the same subnet?

But then also, I'm not so concerned about options - eCos uses thousands of options, and it works fine. What matters is not the number of options, but organising them into functional groups, sensible defaults and a good description of what each option does. Most people know to leave stuff with the default unless they need to change it.

Jonathan Larmour <jifl>
Project Member
Wed 30 May 2007 10:59:34 AM UTC, comment #15: 

>I'm a little concerned at the moment at the number of optional bits of code we're adding to lwIP.


I've thought of that too :-(

>[..]nor change the array to a list. So one alternative instead is that every time you get a match, swap the array entry with the one before it (until it's at the start).


The redundant code could be avoided if we swap array entries. But that would include copying 2 entries of 16-20 bytes every time. Re-linking a list would be much faster at the downside that access to list items is slower.

2 questions:
a) is converting the array to a list really not an option?
b) should this swapping be a configuration option or always on?

To avoid swapping there and back with concurrently active connections, we could still compare the ctimes...

Simon Goldschmidt <goldsimon>
Project AdministratorIn charge of this item.
Wed 30 May 2007 09:25:17 AM UTC, comment #14: 

Sounds like a good compromise.  I'm a little concerned at the moment at the number of optional bits of code we're adding to lwIP.  This isn't the place to discuss it, but we risk ending up with a lot of not-regularly-tested/unused code, and (more) confused users.

Kieran Mansley <kieranm>
Project Member
Wed 30 May 2007 09:21:20 AM UTC, comment #13: 

I agree with the approach in #12.

But about the hash tables, it seems unlikely in general to me to require ARP tables that size. Most people do not need simultaneous communication on the local subnet to that many hosts. That must be for a very specific and uncommon application.

Jonathan Larmour <jifl>
Project Member
Wed 30 May 2007 09:00:27 AM UTC, comment #12: 

OK, so in a first step, I'll convert find_entry to return a pointer, in a second step, I'll integrate the sorting list as an option.

The hashtable is really optional, since it is only useful for real big ARP tables.

Simon Goldschmidt <goldsimon>
Project AdministratorIn charge of this item.
Wed 30 May 2007 08:45:20 AM UTC, comment #11: 

> Replacing the simple table with a hash table: not so obviously good for lwIP.


That depends:

> Undoubtedly faster (and so more lightweight on the CPU)


Only if generating the hash is faster than scanning the table, so only for big tables.

> but more memory required (and so less lightweight on the memory).


OK, but if you need ~100 entries, the table is also big. I'd say if  someone wants many entries, a hash table is still a good idea.

Nevertheless, this would of course be an option since for 10 entries, the table & one-entry-cache is still the best solution. Also my first optional implementation would be the sorting list, not the hash-table. I think that this is best for sizes between 20 and 50 with some concurrent connections.

Simon Goldschmidt <goldsimon>
Project AdministratorIn charge of this item.
Wed 30 May 2007 08:05:29 AM UTC, comment #10: 

Converting the index to a pointer: no problem, good idea.

Replacing the simple table with a hash table: not so obviously good for lwIP.  Undoubtedly faster (and so more lightweight on the CPU) but more memory required (and so less lightweight on the memory). 

Kieran Mansley <kieranm>
Project Member
Wed 30 May 2007 07:40:06 AM UTC, comment #9: 

> Except that, replace "arp_table[i]" by a pointer should have a high cost. But like each change, do some measures can help to decide if the patch is good or no...


I can't really measure that. In my disassembly, accessing arp_table[i] is done loading the address of arp_table into a register, adding i*sizeof(arp_entry) to it and then accessing the members of the struct with a 'load addr+offset' instruction. In that case, a pointer is better because adding of i*sizeof(arp_entry) is not needed and 'load addr+offset' for the struct members is the same. So now I could do some measurement comparing arp_table[i] to arp_entry* but that would only tell me what's better on my target. That's why I wanted to hear some other opinions...

Can you give me more details why you think the pointer has a higher cost?

> The problem is more to know if it's need to improve that or not.


You mean adding a hash table? That's dependent on how you use lwIP. The current implementation is really slow (unless you have a table with only 10 entries, but that way, you easily end up throwing away entries you would need later...). The recently added one-entry-cache speeds up things if you talk to one host only. Including a hash-table is much too big for some embedded targets, of course. But it's the way most switches to that work, so it can't hurt for lwIP. It depends on the table size. If you have a table with 100 entries, calculating the hash is faster. And I still would add the linked list which is automatically sorted each time it is accessed (moving the wanted entry one step forward, that way entries that are used often are at the beginning of the list).

All that requires that we can use the arp_entries without accessing it like arp_table[i]...

Simon Goldschmidt <goldsimon>
Project AdministratorIn charge of this item.
Wed 30 May 2007 07:22:34 AM UTC, comment #8: 

The problem is more to know if it's need to improve that or not. If your device mainly send to one destination, the current patch is enough. If you receive lot of packets, maintain the hash table can cost a lot. So, I think it's dependant of the use of the stack.

Except that, replace "arp_table[i]" by a pointer should have a high cost. But like each change, do some measures can help to decide if the patch is good or no...

Frédéric Bernon <fbernon>
Project Member
Wed 30 May 2007 07:11:21 AM UTC, comment #7: 

I'd like to have an opinion from other developers on the following: Currently, it's pretty hard to change the table structure in etharp.c, since the use of arp_table[i] is spread all over the file. I plan to change this by letting find_entry return a pointer to an entry instead of an index to the table. That way, only find_entry() and the timer function (maybe that can be changed too, by some kind of define) have to know the structure of the 'table' so only those functions need to be changed to implement e.g. a hash table.

Do any of you have something against that change? I.e. would it make the code slower to work with a pointer instead of a table index? (I think it doesn't but I want some other opinions before changing that)

Simon Goldschmidt <goldsimon>
Project AdministratorIn charge of this item.
Fri 04 May 2007 08:22:36 PM UTC, comment #6: 

I've checked in a simple single entry cache. Not much, but this should help for packet bursts, at least.

Simon Goldschmidt <goldsimon>
Project AdministratorIn charge of this item.
Fri 27 Apr 2007 07:23:02 PM UTC, comment #5: 

OK, http://lists.gnu.org/archive/html/lwip-devel/2006-04/msg00000.html suggests to disable ARP table update from incoming IP packets. Still, ARP broadcasts (gratuitous ARP?) could, on a big network like we have for testing, fill the ARP table, so I made it quite big which slows it down.

I would implement the one-entry cache and optionally including a list instead of an array to allow fast reordering of the entries. When find_entry gives back a pointer to a struct etharp_entry instead of an index, this could be switched mostly by including a different find_entry() function.

I'd make this a compiletime option as I think on really small networks the array is still the best solution (and of course, the smallest, regarding code size).

As to

>in current implementation, ethhdr->type is hardcoded to ETHTYP_IP)


I think renaming etharp_output() to etharp_output_ip() should be enough since etharp is only used with IP packets... But then again, this would unnecessarily break the ports, so I'll guess we'll leave it like it is.

Simon Goldschmidt <goldsimon>
Project AdministratorIn charge of this item.
Fri 27 Apr 2007 01:17:41 PM UTC, comment #4: 

Any cache will have bad cases, there is no perfect solution.  I think a one entry cache is a good compromise between performance and extra memory usage.

An alternative would be to make the table a linked list rather than an array, and just move the current entry to the head of the list.  This should keep the entries used most near the front, and  not require a great overhead as its just pointer manipulation rather than copying whole entries.

Kieran Mansley <kieranm>
Project Member
Fri 27 Apr 2007 01:06:15 PM UTC, comment #3: 

I also think this should be an option as it definitively increases code size, yes.

>I've implemented a simple one-entry cache to find_entry() (the actual code was suggested by somebody else).


That's what I have also thought of as a simple implementation...

Swapping the array entries could be a good idea, but a) you copy 2 whole entries every time sending a packet and b) you could end up switching there and back again using 2 simultaneous connections!

Simon Goldschmidt <goldsimon>
Project AdministratorIn charge of this item.
Fri 27 Apr 2007 12:51:56 PM UTC, comment #2: 

There was discussion about etharp performance on lwip-devel back in 2004, see this thread http://lists.gnu.org/archive/html/lwip-devel/2006-04/msg00000.html.

I've implemented a simple one-entry cache to find_entry() (the actual code was suggested by somebody else). This speeds up performance for the case where lwIP is communicating with one host. I've attached a patch against 1.2.0 release if somebody is interested about it (I've modified my etharp.c so the line numbers are probably off, but you should get the idea).

If lwIP is communicating with several hosts bubbling up the least recently used host on the array like Joanathan suggested is probably the simplest solution.

(file #12607)

Atte Kojo <kojo>
Fri 27 Apr 2007 12:09:19 PM UTC, comment #1: 

Just a general thought about the first point: lwIP uses simple lists and arrays in lots of places for the reason that the memory overhead is small. Something like an RB tree would be much faster, but not really in the lwIP ethos. So anything more complex may need to be an option, depending on how it's implemented.

One simple way to improve things without memory penalty would be on the basis that commonly used destinations would be found faster if they were nearer the start of the array. We don't want to potentially re-sort the array every time we get a request though, nor change the array to a list. So one alternative instead is that every time you get a match, swap the array entry with the one before it (until it's at the start). Commonly used hosts will then rapidly gravitate to the start of the table.

In fact, if the number of destination hosts is small, which I think it probably is in practice for most users, an RB tree (for example) would be slower on average than this.

Jonathan Larmour <jifl>
Project Member
Fri 27 Apr 2007 11:50:15 AM UTC, original submission:  

- Implement faster method than array search to prevent going through the whole ARP table on sending a packet
- Introduce function like etharp_send(netif, pbuf) that fills in the header (used at least twice) to reduce code size.
- Don't know if that's needed: make ARP independent of IP protocol (in current implementation, ethhdr->type is hardcoded to ETHTYP_IP) but that should be OK like it is, I think.
- ARP_QUEUEING: don't queue pbuf if etharp_request() fails with ERR_MEM?

Simon Goldschmidt <goldsimon>
Project AdministratorIn charge of this item.

 

Attached Files
file #13198:  etharp_minor_tuning.txt added by jgrubb (758B - text/plain - minor code size improvement)
file #13146:  etharp_send.patch added by goldsimon (11KiB - text/x-patch)
file #13144:  etharp_addrhint2.patch added by goldsimon (12KiB - text/x-patch)
file #12960:  addr_hint.patch added by goldsimon (26KiB - text/x-patch)
file #12607:  etharp.patch added by kojo (2KiB - text/x-diff - etharp one-entry cache)

 

Depends on the following items: None found

Items that depend on this one: None found

 

Carbon-Copy List
  • -email is unavailable- added by jgrubb (Updated the item)
  • -email is unavailable- added by fbernon (Posted a comment)
  • -email is unavailable- added by kieranm (Posted a comment)
  • -email is unavailable- added by jifl (Posted a comment)
  • -email is unavailable- added by goldsimon (Submitted the item)
  •  

    Do you think this task is very important?
    If so, you can add your encouragement to it.
    This task has 0 encouragements so far.

    Only logged-in users can vote.

     

     

     

    Follow 18 latest changes.

    Date Changed by Updated Field Previous Value => Replaced by
    2007-07-02 goldsimon StatusIn Progress => Done
        Percent Complete50% => 100%
        Open/ClosedOpen => Closed
    2007-06-30 goldsimon Percent Complete10% => 50%
    2007-06-29 jgrubb Attached File- => Added etharp_minor_tuning.txt, #13198
    2007-06-24 goldsimon Attached File- => Added etharp_send.patch, #13146
    2007-06-24 goldsimon Attached File#13145 => Removed
    2007-06-24 goldsimon Attached File- => Added etharp_send.patch, #13145
    2007-06-24 goldsimon Attached File- => Added etharp_addrhint2.patch, #13144
    2007-06-08 goldsimon Percent Complete0% => 10%
    2007-06-05 goldsimon Attached File- => Added addr_hint.patch, #12960
    2007-05-30 goldsimon Should Start On2007-04-27 => 2007-06-27
        Priority1 - Later => 3 - Low
        StatusNone => In Progress
        Assigned toNone => goldsimon
        Effort0.00 => 10.00
    2007-04-28 kojo Carbon-CopyRemoved 51921 => -
    2007-04-27 kojo Attached File- => Added etharp.patch, #12607

    Back to the top


    Powered by Savane 3.5