[ruby-core:69726] [Ruby trunk - Misc #10278] [RFC] st.c: use ccan linked list

Issue #10278 has been updated by Eric Wong.

File 0001-st.c-use-ccan-linked-list-v2.patch added

~~~
Updated v2 patch.

I care about this more, now, since I want to try to make unordered hash an
option with st.c in the future for internals.  This should make future changes
easier-to-understand with less code.

I'm willing to trade a little hash iteration (rare, I hope) performance
for better insert/delete performance (on big hashes).

Also, this has minor object size reductions (on 32-bit x86)

   text    data     bss     dec     hex filename
  14718      24       0   14742    3996 st.o-before
  14166      24       0   14190    376e st.o-after
~~~


----------------------------------------
Misc #10278: [RFC] st.c: use ccan linked list 
https://bugs.ruby-lang.org/issues/10278#change-53107

* Author: Eric Wong
* Status: Assigned
* Priority: Normal
* Assignee: Eric Wong
----------------------------------------
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:

	http://80x24.org/bmlog-20140922-032221.13002

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.

	vm2_bighash*	1.222

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 :<

	hash_keys	0.978
	hash_values	0.941

However, hash_keys/values regressions are pretty small.

Things that worry me:

	vm1_attr_ivar*	0.736
	vm1_attr_ivar_set*	0.845

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--------------------------------
0001-st.c-use-ccan-linked-list.patch (13.1 KB)
0001-st.c-use-ccan-linked-list-v2.patch (16.8 KB)


-- 
https://bugs.ruby-lang.org/