RBTree alternatives because it's bugged and unmaintained

[kyrylo]

Last month I hit a bug with TDigest on CRuby:

[3] pry(main)> Marshal.dump(TDigest::TDigest.new)
TypeError: instance of IO needed
from (pry):3:in `_dump'
[4] pry(main)>

This happens because RBTree is bugged (it cannot be dumped either). I've patched it in skade/rbtree#2 but it's highly unlikely that the PR will be reviewed, merged and released any time soon. RBTree is unmaintained.

I checked the implementation of the TDigest library and it seems like RBTree can be replaced with any other kind of tree, it's not a strict requirement.

It's important to make TDigests dumpable because it's a basic data structure and it'll be used by many other objects. What would you advise me to do?

[wallin]

Hi @kyrylo, thanks for pointing this out.

Is there any reason you don't want to use the built in serialization?
https://github.com/castle/tdigest#serialization

[kyrylo]

Thanks for the fast reply (honestly didn't expect 😁).

I don't dump tdigests anywhere in my code but users of my library do. I have no control over that. I am likely missing something but I am not sure how to switch to the built in serialisation. It doesn't seem to be obvious from the documentation.

Could you point me out to the relevant bits?

[lukeasrodgers]

@wallin I am one of those users :)

Basically I have an application that uses another gem which uses Marshal.dump for a ruby sorted set (https://github.com/bokmann/business_time/blob/022347ed0f92d09d01ea76064c8ceca18d74726e/lib/business_time/config.rb#L208) -- ruby's sorted set uses rbtree if its available (https://github.com/ruby/ruby/blob/trunk/lib/set.rb#L710). So if rbtree is available, and you try to marshal dump a sorted set, you'll get the error @kyrylo is discussing.

[wallin]

Hi @lukeasrodgers,

Would you be able to use the built-in serialization instead? It's much more efficient and optimized, and it's documented in the original T-digest paper. eg:

https://github.com/castle/tdigest/#serialization

serialized = tdigest.as_bytes
tdigest = TDigest::TDigest.from_bytes(serialized)

[wallin]

An alternative would be to implement custom Marshal behavior for a TDigest, what will use the proper serialization/deserialization. Would that work you?

[lukeasrodgers]

@wallin the problem is that the de/serialization is not in my code, it's in a dependency. So basically, if I have dependency A which uses Marshal.dump on a SortedSet, and dependent B which requires (transitively or otherwise) RBTree, then Marshal.dump in dependency A is now broken. TDigest itself is not the problem, it's just the bare fact that it depends on rbtree at all.

I appreciate your efforts to dig into this @wallin! I know it is always frustrating to have to concern yourself with other people's dependency hell problems.

I'm not familiar with TDigest (or really rbtree internals, for that matter) but it strikes me that for this particular problem, the only solutions would be:

1. me avoiding dependency B (i.e. @kyrylo's code) -- this is what I am currently doing
2. me avoiding dependency A -- not an option for me, at the moment
3. monkeypatching dependency A to not Marhsal.dump the SortedSet, or something along those lines -- possible, but undesirable and I'd probably only go this route if I really needed dependency B
4. have TDigest not depend on rbtree, as @kyrylo suggested
5. have @kyrylo's fix merged into rbtree -- unlikely to happen

[kyrylo]

@wallin I don't think #6 (comment) will work. @lukeasrodgers explained this well. It's not as_bytes that is the problem but Marshal.dump(TDigest::TDigest.new).

I think #6 (comment) could be the answer. That said, I believe the proper fix would be using a fixed RBTree or another tree mechanism. That's what I would look into but I realise it's a long path. If you could implement custom Marshal behaviour that works Marshal.dump, I'm fine with that. It doesn't sound trivial, though 🙂

Basically, this library is prone to this bug and it's really important to fix it, in my opinion:

class MyObj
  def initialize
    @tdigest = TDigest::TDigest.new
  end
end

Marshal.dump(MyObj.new) #=> BOOM

[kyrylo]

@wallin please let me know if you don't have the capacity to work on this gem. I got a few more bug reports identical to this one and I'd like to take an action.

[wallin]

Hi @kyrylo @lukeasrodgers. As you suspected, I currently don't have any capacity to work on this.

If custom Marshal for the TDigest object solves your issues, I'd vote for implementing that. It should be as simple as implementing _dump and _load methods, and aliasing them to the current serialization methods https://ruby-doc.org/core-2.5.0/Marshal.html