Re: When linear search faster hash map
Hello, netch80, you wrote: N> Hello, c-smile, you wrote: CS>> the case Is resulted when O (N) lookup covers O (1) as a bull a sheep. N> in one and a half time (3.44 against 2.13) it "as a bull a sheep"? N> "Well excuse..." (() Vovochka) N> Also we note, only at 9 records the linear search is already worse . And what further? CS>> And over O (log N) - generally continuous violation. N> already on pair tens percent. Well so, here kopeck, there kopeck... N> And if really fast search - that here is necessary as it to do - to look, for example, in Kamailio: N> N>#define _acce_ 0x65636361/* "acce" */N>#define _allo_ 0x6f6c6c61/* "allo" */N>#define _auth_ 0x68747561/* "auth" */N>#define _oriz_ 0x7a69726f/* "oriz" */N>#define _atio_ 0x6f697461/* "atio" */N>#define _call_ 0x6c6c6163/* "call" */N>#define __ id2_ 0x2064692d/* "-id" */N>#define __ id1_ 0x3a64692d/* "-id:" */N> [...] N>#define FIRST_QUATERNIONS \N> case _via1_: via1_CASE; \N> case _from_: from_CASE; \N> case _to12_: to12_CASE; \N> case _cseq_: cseq_CASE; \N> case _call_: call_CASE; \N> case _cont_: cont_CASE; \N> case _rout_: rout_CASE; \N> case _max __: max_CASE; \N> N> well and so on - the line is cut in the standard portions on 4 bytes, translated to the lower register (SIP titles - case-insensitive) and then the compiler task - to select the correct variant to spread out case (normally it builds something like a tree). Yes, it is very rigid target optimization. But there it is justified. Yes here too not the fact actually... 1) endianness 2) transfer in the lower register it O (n) and 3) switch on rarefied case values is all the same linear lookup. A bit better, but nevertheless it is necessary to look at specific allocation tokens probability. About which the compiler does not know anything and can generate bad lookup.