Currently used variant is 'binary search in small table + hash for large tables'.
But for contemporary CPU it may be better to do linear scan for small tables.
It is already implemented in id_table.c and numbered as 35.
Tested with simple Redmine installation on Intel Haswell i7-4770 CPU @ 3.40GHz
trunk: Requests per second: 27.79 [#/sec] (mean)
with switched implementation: Requests per second: 28.87 [#/sec] (mean)
I just install Redmine - the same software that powers bugs.ruby-lang.org ,
then add several test issues, and bench it with 'apache benchmark': ab -n 1000 -c 10 http://localhost:3000/projects/general/issues
(general is a name of test project)
In other words, big web applications are too big for global method cache, and too polymorphic for inline cache.
So general method lookup is inevitable.
With current choice for id_table implementation (34) it takes about 4.5-6%CPU.
With implementation 22 it takes just 2.5-3% CPU.
Excuse me for not reacting on discussion.
I forgot to turn on mail notifications for this issue.
can you make a table more small with a few entries?
It could be 25% smaller for any size (on x86_64) at cost of second memory lookup
if key and value stored in separate arrays. It should be measured.
Single pointer still could be used as with "USE_CALC_VALUES".
ko1, will you just switch id or remove other implementations?
if first, I may prepare patch for current source, otherwise I will wait for commit.
Oh, to reduce hash size either max serial_id should be 0x7fffffff instead of 0xffffffff
(cause 1 bit is stolen for collision check),
or collision bit removed (it will increase time for "miss" and decrease for "hit").
Yura:
Sorry for my laziness. I committed it (remain only your algorithm) and cleanup source code.
Pls make another ticket to improve id_table structure.