I took my algorithms class from one of the inventors of fusion trees. It’s
more of a stunt than anything else. He invented it just to prove the point.
The constant factor of each operation dwarfs the comparison it avoids. But
the big-O is relatively small. They are still impractical.
Pico operates on lists. Its fundamental data structure tends toward linear
algorithms. Trees are also possible where needed. In general, this is not
the fastest, but it’s usually good enough.
On Sun, May 3, 2020 at 16:57 Guido Stepken <gstep...@gmail.com> wrote:
> 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.wikipediaorg/wiki/Fusion_tree>
> ²) https://en.wikipedia.org/wiki/Exponential_tree
> ³) https://en.wikipedia.org/wiki/Fenwick_tree
> ⁴) https://graphics.stanford.edu/~seander/bithacks.html
> <https://graphics.stanford.edu/~seander/bithackshtml>
--
John Duncan
