matthewhammer
commented
2 years ago Thanks for this report, @ByronBecker!
I wonder if you could repeat the experiment with another existing base structure in place of the red-black tree.
If you are only inserting, for instance, it would be interesting to use lists, and always prepend (in constant time). Since we know that will always be constant time, it would be an interesting comparison to see what limit, if any, you reach with that data structure in place of where you currently use the RBTree. WDYT?
BTW -- I have been preoccupied with family life recently, but still plan to implement the imperative B-Tree asap. Of course, that comparison will be interesting too, when we can do it.
ByronBecker
ggreif
crusso
timohanke
@matthewhammer @crusso
I've recently moved from doing local testing to main network testing, and one of the large difference between testing locally and on the main network are limitations such as the instruction limit for single message execution.
The issue
On the main network, at a certain point (less than the canister heap size or the canister memory size), Red-Black Trees are unable to insert more records and hit the instruction limit for single message execution.
The error.
Once I have around 290-500MB (heap size) memory in my canister, insertions of ~30-80KB per message will randomly start to return the following error
What I was doing at the time of the error
For example,
At this heap utilization, I was chunk uploading 100 rows at a time (30-80KB), and then inserting in the manner shown in the "Some Context" section below. All of a sudden, I received the error shown in the "The issue" section above, and was no longer able to perform insertions into the Red-Black Tree without receiving that error. I was able to upgrade the canister and update other stable variables, but nothing more could be inserted into the Red-Black tree.
I even made a special csv with just 1 row at this point and tried to insert it into the Red-Black Tree on this 484MB heap sized canister and still received the same error
The script I run
My guess is that this could either be due to inefficiencies in re-balancing the Red-Black Tree, or that the tree has gotten so deep that recursive operations are much more costly by (more than linear factor) due to the call stack or some other factor.
Some More Context
My database project, CanDB, is a Red-Black tree of type
<Text, AttributeValue>whereAttributeValueis a stable primitive.I'm testing out backfill-ing a large amount of data into CanDB, from which ~80KB csv chunks are formatted and uploaded to the following API endpoint,
processComments().(For reference, the awaits in the
CanDB.put()method are only ever called once in a canister's lifetime, and this is for scaling out a new canister. This means that everyCanDB.put()method is synchronous except in the one time it needs to signal that it needs to be scaled out)If you are interested in the code for
CanDB.put(), you can find it here, and theRangeTreedata structure that sits on top of a Red-Black as well.Recommendations
I'm curious if digging into the recursive (performance) aspects of the functional data structures in motoko-base might find "easy-win" areas of improvement to avoid the message execution instruction limit.
Also, in addition to the local testing, it would be a good idea to do some main network testing with respect to the performance of imperative, mutable data structure implementations (Red-Black Tree, BTree) against their functional counterparts.
My takeaways
While I enjoy many of the functional aspects and guarantees of the implementations, if I'm releasing a database product the bottom line for me a data structure that provides consistent performance.
In the coming weeks, I'm also going to test the limitations a bit more, as well as look to see if I can make certain optimizations like putting a short hash table or Trie at the top that might reduce any rebalancing or stack depth issues.