Misc #10278
closed
[RFC] st.c: use ccan linked list
Description
Mainly posting this for documentation purposes because it seems like
an obvious thing to try given we have ccan/list nowadays.
Having shorter code along branchless insert/delete, and using a common
linked-list API is very appealing.
On the other hand, benchmark results are a mixed bag:
Also, I may have introduced new bugs the tests didn't catch.
The st_foreach* functions get a bit strange when dealing with
packed-to-unpacked transitions while iterating.
Great thing: bighash is faster (as expected) because of branchless
linked list insertion. However, the major speedup in bighash probably
isn't too important, most hashes are small and users never notice.
Also, we could introduce rb_hash_new_with_size() for use insns.def
(newhash) if people really care about the static bighash case (I don't
think many do).
Real regressions, iteration seems more complex because loop conditions
are more complex :<
However, hash_keys/values regressions are pretty small.
Things that worry me:
WTF? I reran the attr_ivar tests, and the numbers got slightly better:
["vm1_attr_ivar",
[[1.851297842,
1.549076322,
1.623306027,
1.956916541,
1.533218607,
1.554089054,
1.702590516,
1.789863782,
1.711815018,
1.851260599],
[1.825423191,
1.824934062,
1.542471471,
1.868502091,
1.79106375,
1.884568825,
1.850712387,
1.797538962,
2.165696827,
1.866671482]]],
["vm1_attr_ivar_set",
[[1.926496052,
2.04742421,
2.025571131,
2.047656291,
2.043747069,
2.099586827,
1.953769267,
2.017580504,
2.440432603,
2.111254634],
[2.365839125,
2.076282818,
2.112784977,
2.118754445,
2.091752673,
2.161164561,
2.107439445,
2.128147747,
2.945295069,
2.131679632]]]]
Elapsed time: 91.963235593 (sec)
-----------------------------------------------------------
benchmark results:
minimum results in each 10 measurements.
Execution time (sec)
name orig stll
loop_whileloop 0.672 0.670
vm1_attr_ivar* 0.861 0.872
vm1_attr_ivar_set* 1.255 1.406
Speedup ratio: compare with the result of `orig' (greater is better)
name stll
loop_whileloop 1.002
vm1_attr_ivar* 0.987
vm1_attr_ivar_set* 0.892
Note: these tests do not even hit st, and even if they did, these are
tiny tables which are packed so the linked-list implementation has no
impact (especially not on lookup tests)
So yeah, probably something messy with the CPU caches.
I always benchmark with the performance CPU governor, and the
rerun ivar numbers are run with CPU pinned to a single core.
CPU: AMD FX-8320 Maybe I can access my other systems later.
Files
Updated by 
Updated by