open62541 VS bst

Zip trees are great!

For a project I made a version that uses the memory location of the entries to construct the (random) rank on the fly.

So it’s a binary tree structure that requires the same memory as a linked list (two pointers) only!

https://github.com/open62541/open62541/blob/master/deps/zipt...

Here is a bug report I submitted to open62541, over a year ago. Figuring out how that library works... I don't even understand the terminology; it's all very generic (everything is called 'nodes', 'objects', etc.), there are loads of ways to do anything, type safety is not a concept the library approves of so that doesn't help either, and most functions you cannot even find in the source as they are generated by macros. It doesn't help that OPC UA is a big standard (thousands of pages) either. It boggles the mind that the reference implementation for something used in so many critical places is so badly documented, and at the same time allows so many ways to get things subtly wrong.

There's quite a bit of OPC UA bashing across this project. So let me chime in to keep the "balance in the universe".

OPC UA is a protocol to interact with an object-oriented information model. Basically CORBA done right to use object-oriented principles and reuse software components in industrial automation.

Since OPC UA is a protocol, its performance depends mostly on the implementation. Some PLCs may be crappy. But that doesn't translate into bad performance overall. My experience goes to the exact contrary.

Full disclosure, I lead-develop and maintain an open source OPC UA implementation that sees quite a bit of use by the big guys in the automation domain. We use C for performance. And we do have funding from the industry.

https://github.com/open62541/open62541

But yes, it is hard to break into this world. Especially since solutions have to be maintained for 20+ years. A solo developer usually cannot ensure that this will still be usable some years down the line.

Earlier this year I was trying to use open62541, and ended up writing this bugreport. The developers are, so far, ignoring it, and it's a crying shame because it makes the library so much less useful than it could otherwise be.

Why don't you use a standardized industrial protocol, that support these requirements? Would perhaps OPC UA meet your needs? There are a number of open source implementations and the standard itself is open, too.

Zip trees are novel but their performance (and therefore also skip lists, since they are isomorphic) lacks behind other linked structures like Treaps and especially LBSTs. [1] I personally find skip lists to be overhyped binary search trees in disguise.

[1] https://rtheunissen.github.io/bst

Thank you for sharing this resource, I was not aware of it. I am happy to see the inclusion of LBSTs there too.

Re: binary symmetry, if I'm understanding correctly, another author that makes use of the symmetry is Ben Pfaff in libavl [1]. At the top of [2], which seems a bit misplaced now, I wrote:

> A choice was made to not unify the symmetric cases using the direction-based technique of Ben Pfaff and others because it makes the logic more difficult to follow even though there would be less code overall.

The choice of Go was to provide implementations that are both reliable to benchmark (though not as robust as C or Rust for example) but also easy to read. I would like to further reduce abstraction by decomposing common parts such that all the strategies are "one-file" references. This is then effectively the opposite of what the macro-based implementation achieves. Both have value, of course.

[1] https://adtinfo.org/libavl.html/BST-Node-Structure.html

[2] https://github.com/rtheunissen/bst/blob/main/trees/avl_botto...