How to test parallel operations? (trouble with synchronization)

Developers Motoko
1

I have two trees: testedTree and referenceTree. With the purpose of debugging testedTree I do the same changes (like adding/deleting a node) to both trees and then compare them.

referenceTree is a regular RB-tree. testedTree is controlled by shared calls.

Sometimes my code outputs that tree are not equal, but probably it is a false positive due to the following:

func add() : async () {
  ...
  await testedTree.add(x, y);
  referenceTree.add(x, y);
};

func del() : async () {
  ...
  await testedTree.del(x);
  referenceTree.del(x);
};

The problem is that the order in which referenceTree.add(x, y); and referenceTree.del(x); calls happen is unspecified, so I can get wrong referenceTree!

The question is how to fix this test bug.

I can’t put a lock around add and del calls, because it undetermines the purpose of my test: to run several add and delete operations simultaneously (to the point of them being run only between awaits, as usual).

So, how to rewrite this test?

2

As written, it looks like ‘add()’ and ‘dell()’ are both fire-and-forget in the sense that their caller cannot wait for them to complete. Is that intentional? To make them awaitable, they need to have an explicit ‘async ()’ return type

3

I have corrected the type of the functions.

4

If that doesn’t fix, then maybe show a bit more context (i.e. the test driver) so forum readers can pitch in.

5

Also are you sure it’s correct to update the reference tree after updating the tested tree, which allows for interleaving?

6
7

I just need to run update both trees by the “same” operations in the same order.

The only problem is that I don’t know how to ensure that the operations for both trees run in the same order.

8

Ok, that’s a lot of code ;->

The IC is support to guarantee that messages from A to B arrive at B in the order sent from A.
Can you (perhaps) write a test driver A(B), that deterministically sends the desired sequence of messages to canister B, then run A(B1) and A(B2) and after both complete, compare the states of B1 and B2?

9

I understood nothing: What are B1 and B2? What is A(B)? Etc.

I think, I found solution to my problem: I will add function argument (only for testing) to add and del shared methods. This function will modify referenceTree. This seems the only way to make the order of operations in resultingTree and referenceTree match, because await is always non-deterministic.

10

A was meant to be test harness testing some parameter canister B. B1 and B2 are the reference/actual implementations. But never mind, glad you found an easier solution.