4 ms·

> Many developers implement this logic using simple switch statement. However, after about 7 - 10 cases such dispatch mechanism becomes quite inefficient, and i

by berti 8y ago

> Many developers implement this logic using simple switch statement. However, after about 7 - 10 cases such dispatch mechanism becomes quite inefficient, and its inefficiency grows with number of new messages being introduced. It's actually pretty cheap on ARM (2 cycles [1]), if the message IDs are consecutive, due to TBB/TBH [2], and GCC will use it when appropriate. Not sure if x86 has an equivalent. [1] http://infocenter.arm.com/help/index.jsp?topic=/com.arm.doc.ddi0439b/CHDDIGAC.html http://infocenter.arm.com/help/index.jsp?topic=/com.arm.doc.... [2] http://infocenter.arm.com/help/topic/com.arm.doc.dui0553a/BABJHIGF.html http://infocenter.arm.com/help/topic/com.arm.doc.dui0553a/BA...

bewo001 8y ago
..and his proposed alternative requires that you have already decoded the message to create the corresponding Message objects. To create those objects, you still need some sort of switch somewhere, eg switch(ip.protocol()) { case 6: m = new TcpMessage(); break; case 17: m = new UdpMessage(); break; .. }
vardump 8y ago
Switch is efficient on pretty much any platform I can think of (well, except some 8-bit uC compilers...). That statement about switch inefficiency is simply not true, except for sparse case values. But since one can generally choose those values (and they're often a running enum anyways), it's really a non-issue. For sparse case, it's better to use a hash table. Perhaps a build phase to generate a perfect hash (https://en.wikipedia.org/wiki/Perfect_hash_function https://en.wikipedia.org/wiki/Perfect_hash_function) to map each possible input value to continuous range of integer values.
- brandmeyer 8y ago
  > except for sparse case values Even for sparse case values the compiler will emit a binary search once the list of labels is long enough.
  - convolvatron 8y ago
    i’m pretty sure i’ve heard of compilers generating a perfect hash (since the key space is known) also
    - vardump 8y ago
      This has been my expectation as well, but haven't seen this in real life. I guess the main issue is that the compiler will need to also ensure no value outside the expected set can match a case statement either (no match and default cases), which kinda negates the benefit. Maybe there are cases this is generated, anyone seen compiler generating those? I wonder whether it is possible to generate reversible (almost) perfect "hashes"? I mean a hash where every unique input value is guaranteed to map to a unique output value. Because this kind of hash could be used to handle no-match/default case safely.

by berti 8y ago

bewo001 8y ago

..and his proposed alternative requires that you have already decoded the message to create the corresponding Message objects. To create those objects, you still need some sort of switch somewhere, eg switch(ip.protocol()) { case 6: m = new TcpMessage(); break; case 17: m = new UdpMessage(); break; .. }

vardump 8y ago

Switch is efficient on pretty much any platform I can think of (well, except some 8-bit uC compilers...). That statement about switch inefficiency is simply not true, except for sparse case values. But since one can generally choose those values (and they're often a running enum anyways), it's really a non-issue. For sparse case, it's better to use a hash table. Perhaps a build phase to generate a perfect hash (https://en.wikipedia.org/wiki/Perfect_hash_function https://en.wikipedia.org/wiki/Perfect_hash_function) to map each possible input value to continuous range of integer values.

brandmeyer 8y ago
> except for sparse case values Even for sparse case values the compiler will emit a binary search once the list of labels is long enough.
- convolvatron 8y ago
  i’m pretty sure i’ve heard of compilers generating a perfect hash (since the key space is known) also
  - vardump 8y ago
    This has been my expectation as well, but haven't seen this in real life. I guess the main issue is that the compiler will need to also ensure no value outside the expected set can match a case statement either (no match and default cases), which kinda negates the benefit. Maybe there are cases this is generated, anyone seen compiler generating those? I wonder whether it is possible to generate reversible (almost) perfect "hashes"? I mean a hash where every unique input value is guaranteed to map to a unique output value. Because this kind of hash could be used to handle no-match/default case safely.