Option to disable deduplication

[malthe]

If it's known that objects are unique, there's no point in trying to deduplicate (which, as it is currently implemented, is a rather expensive process.)

In Python, a workaround is currently to simply issue a builder.vtables.clear() call after each object is added to the buffer.

It could be argued that deduplication is not a valid concern for the library at any rate since the application code can easily implement this itself, but that's a different matter.

[aardappel]

Have you profiled and found that de-duplication is your performance bottleneck? What are the exact timings you found? Why are you wanting to turn it off?

It is an important feature for most uses of FlatBuffers, so its certainly not something I'd want the user to have to do himself.

[malthe]

I'm building up a buffer of millions of objects, and after N objects have been inserted, the next operation will examine those N objects in reverse order.

If I was a user who wanted de-duplication, then I'd implement it using some heuristic or index in order to avoid searching through all possible matches.

[aardappel]

It is very rare for there to be a great variety of possible vtable layouts, and in most use cases this number stays very low, to the point that the overhead of an accelerated search data structure would cause more overhead than it removes.

By default, users will want de-duplication.

Have you tested for your use case how many different vtables you end up with? Any actual performance figures?

[malthe]

Perhaps I've totally misunderstood something, but if I have N unique objects (an object is different to another if at least one property is different), then I'll have N vtables. I'm not sure what you mean by vtable layouts – but from what I could tell looking at the code, de-duplication just looks at the raw data to see if a new entry is equal to a previous one.

Let's say that I have N points of interests. They're all different. I don't even want to check for duplicates because I know that they're different. It would be an error if they were not, presumably.

[aardappel]

No, this is not about object contents. Typically 2 objects with similar fields set like { 1.0, "Fred" } and { 2.0, "Bob" } will have identical vtables. In fact, even objects with unrelated types can have identical vtables.

Like I said, don't make assumptions until you profile it :)
Also check out the FlatBuffers docs on how vtables work.

[malthe]

I did profile it – but I can see now that I have misunderstood how vtable de-duplication works. I'll try to find out why I'm getting different vtables for "similar fields", or in other words: why I have vtable explosion.

[malthe]

The mild explosion (see below) seems to stem from having a fair amount of default values at more or less arbitrary positions, causing an initially peak growth in the possible layouts:

Added 10000 rows (803 rows/sec, vtables: 611).
Added 20000 rows (460 rows/sec, vtables: 882).
Added 30000 rows (356 rows/sec, vtables: 1105).
Added 40000 rows (300 rows/sec, vtables: 1283).
Added 50000 rows (264 rows/sec, vtables: 1445).
Added 60000 rows (243 rows/sec, vtables: 1575).
Added 70000 rows (224 rows/sec, vtables: 1712).
Added 80000 rows (208 rows/sec, vtables: 1837).
Added 90000 rows (195 rows/sec, vtables: 1954).
Added 100000 rows (184 rows/sec, vtables: 2069).
Added 110000 rows (176 rows/sec, vtables: 2157).
Added 120000 rows (169 rows/sec, vtables: 2242).
Added 130000 rows (162 rows/sec, vtables: 2339).
Added 140000 rows (156 rows/sec, vtables: 2445).
Added 150000 rows (150 rows/sec, vtables: 2544).
Added 160000 rows (144 rows/sec, vtables: 2630).
Added 170000 rows (139 rows/sec, vtables: 2722).
Added 180000 rows (135 rows/sec, vtables: 2815).
Added 190000 rows (131 rows/sec, vtables: 2883).
Added 200000 rows (128 rows/sec, vtables: 2956).
Added 210000 rows (125 rows/sec, vtables: 3023).
Added 220000 rows (122 rows/sec, vtables: 3096).
Added 230000 rows (120 rows/sec, vtables: 3159).
Added 240000 rows (112 rows/sec, vtables: 3230).
Added 250000 rows (111 rows/sec, vtables: 3319).
Added 260000 rows (109 rows/sec, vtables: 3368).
Added 270000 rows (107 rows/sec, vtables: 3440).
Added 280000 rows (105 rows/sec, vtables: 3515).
Added 290000 rows (103 rows/sec, vtables: 3575).
Added 300000 rows (102 rows/sec, vtables: 3642).
Added 310000 rows (100 rows/sec, vtables: 3698).
Added 320000 rows (98 rows/sec, vtables: 3764).

It is in fact the de-duplication that causes this slowdown. This same process normally has a throughput of about 20,000 rows/sec.

[aardappel]

Ok, that does sound like a crazy amount of vtables. How many fields does your most-used table have? And these are randomly default or not? I've never seen a combinatorial explosion like this in practice.

I did have thoughts in the past to basically switch to a binary tree or hash map once number of vtables goes over a certain amount, and you certainly go over that amount. But yes, if you don't have space concerns then just turning it off may be better in this case. The C++ API has a way to turn it off, it could be added to other languages as well.

Btw, why use Python for such intensive data processing? Having this many vtables would be in issue in other languages as well, but Python will make it more pronounced.

[malthe]

Yeah, now that I understand the vtable layout issue, I think it would make sense to still be able to efficiently reuse/deduplicate even with thousands of vtables.

The choice of using Python mostly for deployment convenience. It's not particularly slow when the number of vtable layouts stays low.

[rw]

@malthe Reminder to please make a PR to improve documentation around the new Python deduplication algorithm