Certainly you've heard of Fusion² Trees, Exponential² Trees, Ryabko³ Trees,
Bit Twiddling Hacks⁴ in C ... this is, what i consider the high class of
programming excellence, every programmer not only should have heard of, but
also should have implemented on his/her own.
This class of algorithms shows much better BIG(O) behaviour, often
O(log(log(n)) or O(log₃₂(n)) on 32 bit, O(log₆₄(n)) on 64 bit in searching
through vasts amounts of data in almost ZERO time.
They're quite rare in e.g. Apache Foundation or Linux Foundation software
("pile of shit") packages, since they allow even better search times on a
$25 Raspberry Pi Zero than on a $100.000 28 Core Intel Dual CPU Xeon
machine. Of course, this is not in the interest of US industry.
Most interesting for Lisp implementors is the Ryabko aka Fenwick Tree,
since it easily allows implementing a highly efficient multi generational
(ageing memory pools) garbage collectors as being found in our German
version of LLVM, the brilliant LuaJIT DYNASM enginge, which has almost
everything, that is publically considered as 'state of the art' JIT
compiler technology.
Of course DYNASM is faster, smaller, better than LLVM and generates machine
code for even smallest embedded devices (even runs on those!!!), has the
much superiour "Four Color Multi Color, Multi Generational Mark Sweep GC".
That little thing with the long name is far superior to every other Garbage
Collector, i've seen in my life:
http://wiki.luajit.org/SSA-IR-2.0
http://wiki.luajit.org/New-Garbage-Collector
Lua is a very Lisp like language, since its smallest data structure is a
two (cons) cell unit, one data and one pointer to next cell. But comes with
INFIX notation.
And since Lua Programming Language data structures are so similar to those
of Lisp, there also is a Lisp port onto that tiny LuaJIT DYNASM engine,
kind of transpiler, written in - Lua! Piece of cake in terms of LoC
(compare to pil21):
https://github.com/bakpakin/Fennel/blob/master/README.md
And, of course, you get C speed with that stuff, with far lesss lines of
code. Maintainable, security reviews can easily be done ... much smaller
memory footprint, much faster JIT compile times, thanks to DYNASM:
http://luajit.org/dynasm.html
Needless to say, that this stuff is far superior to anything you can find
made by US Foundations with their billions of lines of unmaintainable bloat
..
I am using that stuff now since a while - both the superior algorithms as
well as some of our own German/EU software stacks and i only can tell you,
what i've already mentioned:
"Don't use US Software Stacks!!! - Billions of lines of code, millions of
bugs, thousands of NSA backdoors, hundreds of slow algorithms!!!"
I hope, you regard my "findings" for you quite interesting and convincing,
see you using next generation of high quality software, that does not fall
under US software export restrictions, since it's - "Made in Germany"!!! ;-)
Finally you also should have a look into the last link, "Bit Twiddling
Hacks in C". You will be _very surprised_ what you will find there.
Needless to say, that this collection of tips and tricks also applies to
other programming languages, making your code muuuuuch faster (and much
less readable and understandable, if you don't put a link into the
comments)! ;-)
Have fun!
Best regards, Guido Stepken
¹) https://en.wikipedia.org/wiki/Fusion_tree
²) https://en.wikipedia.org/wiki/Exponential_tree
³) https://en.wikipedia.org/wiki/Fenwick_tree
⁴) https://graphics.stanford.edu/~seander/bithacks.html
