Certainly, Fusion Tree, as well as the successor, Exponetial Tree and
especially Van Emde Boas Tree have certain "overhead". But it pays off
quickly at search through huge data on terabyte+ SSDs, you even can find in
any home today.
Remember: "You'll never become a car even if you put your body in a garage!"
Regards, Guido Stepken
Am Sonntag, 3. Mai 2020 schrieb John Duncan <duncan.j...@gmail.com>:
> 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.wikipedia.org/wiki/Exponential_tree
>> ³) https://en.wikipedia.org/wiki/Fenwick_tree
>> ⁴) https://graphics.stanford.edu/~seander/bithacks.html
>
> --
> John Duncan
