Hi, Two things, one from last night...
djbsort claims sorting record for in-memory sort of 32-bit signed integers. https://sorting.cr.yp.to/index.html The technique is buried in Appendix S, page 48, of https://ntruprime.cr.yp.to/ntruprime-20170816.pdf It uses a https://en.wikipedia.org/wiki/Sorting_network where each node takes (a, b) and computes (min(a, b), max(a, b)). The speed is achieved by using the AVX2 CPU's vector instructions to do 8×32b min() in parallel, ditto max(), and using the vector-permute instructions to get the a's and b's in the right place. https://en.wikipedia.org/wiki/AVX2#Advanced_Vector_Extensions_2 It can sort 1Ki×32b sitting in L1 cache at 10 cycles/32b. Due to the sorting network and vector instructions, it's constant time. ...and the other from IRC follow-up this morning. `sudo -i perf top --fields overhead,cpu,comm,dso,symbol' shows the symbols in libraries and executables that are consuming CPU on the machine, e.g. xfce4-terminal using libglib-2.0.so.0.5600.1's g_array_append_vals() function. Cheers, Ralph. -- Next meeting: Bournemouth, Tuesday, 2018-08-07 20:00 Meets, Mailing list, IRC, LinkedIn, ... http://dorset.lug.org.uk/ New thread: mailto:dorset@mailman.lug.org.uk / CHECK IF YOU'RE REPLYING Reporting bugs well: http://goo.gl/4Xue / TO THE LIST OR THE AUTHOR
