π-WAM Contest: 1 Million Packets with Prolog

We recently demonstrated a Prolog emulator for ADA RendezVous without ACK and NACK. This is basically a bounded buffer with max_size=1. We now went on and implemented this kind of fire and forget channel object natively for JavaScript, Java and Python. Some results.

Native RendezVous

Our native channel object uses two semaphores. We found such classes in Java and Python and could use them in our realization. For JavaScript we had to juggle with Atomics, but could also implement native blocking and non-blocking variations using wait() and notify().

We will briefly review the Java realization, to show the difference between the blocking and non-blocking variants. Both the blocking and non-block variants use the same semaphores. The realization is based on the fact that semaphores can also be operated blocking and non-blocking.

public final static class RendezVous {
    private final Semaphore head = new Semaphore(0);
    private final Semaphore tail = new Semaphore(1);
    [...]
}

The tail semaphore indicates an empty while the head semaphore indicates a full. Two semaphores allow a transition time, where the leading task can store the data, before the recipient load the data. The skeleton of the blocking channel object API put/take reads:

public static void cpu_chan_put(RendezVous chan, /* more */)
        throws InterruptedException {
    chan.tail.acquire();
    /* store */
    chan.head.release();
}

public static void cpu_chan_take(RendezVous chan, /* more */)
          throws InterruptedException {
    chan.head.acquire();
    /* load*/
    chan.tail.release();
}

To arrive at the channel object API offer/poll that would be non-blocking, one has to simply replace the semaphore calls acquire(), by tryAcquire(). Some APIs lump sum the behaviour blocking and non-blocking via a timeout parameter, that can be zero or infinite.

Static Buffers

In some of our tests, we observed that a JavaScript worker run out of memory. This was an early propotype of our channel objects, that was very Java stylish, namely each ADA Redezvous created a new int[] object, since the data inside the RendezVous was only a object pointer.

To adress this problem of memory pressure and subsequent consequences for host language native and parallel garbage collection, we decided to postulate a maximum buffer size, and provide the exchange buffer inside the RendezVous object itself:

private static final int MAX_DATA = 128;

public final static class RendezVous {
   [...]
   private final int[] data = new int[1+MAX_DATA];
}

The π-WAM generated already exchange buffer friendly code, we only had to utilize it when adding channel object support inside the π-WAM. Since packets can nevertheless have varying sizes, and we want packets to be transfered atomically, we simply store the size in data[0]:

private static void cpu_data_store(int[] data, int max, 
                                   int[] state, int base) {
    data[0] = max;
    for (int i = 0; i < max; i++)
        data[1+i] = state[base+i];
}

private static void cpu_data_load(int[] data, int max, int[] state, int base) {
    int len = data[0];
    for (int i = 0; i < max; i++)
        state[base+i] = (i < len ? data[1+i] : 0);
}

For the load we decided on a compromise. Since a π-WAM receive expects a certain size, but the arrived data might have a different size. The error free approach here is to either crop the arrived data, or to pad the arrived data with additional zeros. As shown above this logic is straight forward.

SWI-Prolog Million

As an early benchmark and showcase we exchanged 1 Million = 10⁶ Packets with Prolog. And to make it more interesting we used the threads and message queues from SWI-Prolog, with all their default settings. Means we used queues that were blocking and unbounded.

Get Dogelog Player’s stories in your inbox

Join Medium for free to get updates from this writer.

Remember me for faster sign in

The SWI-Prolog code has first a π-WAM execute/2 polyfill:

execute(G, [size(N)]) :-
   length(T, N),
   maplist(thread_create(G), T),
   maplist(thread_join, T).

The above polyfill is then used in a producer consumer scenario. Each producer/consumer puts/takes 10000 = 1⁴ packets. By invoking 100 producers and 100 consumers, we exchange 100*10000 = 10²*10⁴ = 10⁶ packets, that is 1 million packets.

producer(C) :-
   execute(
      (between(1,100,_),
      between(1,100,_),
      thread_send_message(C,[0]),
      fail; true), [size(100)]
   ).

consumer(C) :-
   execute(
      (between(1,100,_),
      between(1,100,_),
      thread_get_message(C,[0]),
      fail; true), [size(100)]
   ).

test :-
   message_queue_create(C),
   thread_create(producer(C), _),
   consumer(C),
   message_queue_destroy(C).

On our AI Laptop, SWI-Prolog 10.1.13 can do that in less than 1 second:

π-WAM Million

We run the same test with π-WAM in Dogelog Player. This time the queue is non-blocking and has a bounded buffer with max_size=1. The code looks similar to SWI-Prolog, except the channel objects have a different factory, are garbage collected and are adressed by numbers:

:- ensure_loaded(library(misc/brainfog)).

producer(C) :-
   execute(
      (between(1,100,_),
      between(1,100,_),
      send(3,[0])), [size(100), comm([C])]
   ).

consumer(C) :-
   execute(
      (between(1,100,_),
      between(1,100,_),
      recv(3,[0])), [size(100), comm([C])]
   ).

test :-
   cpu_chan_new(C), create_task(producer(C)), consumer(C).

To have multiple π-WAM running inside the multithreaded part of Java, we use create_task/1 from our Dogelog Player cooperative multitasking arsenal. The π-WAM channels apply a polling round robin on the Hack VM instraction level among a groups of logical threads:

π-WAM beats SWI-Prolog here by a factor of ca. 1.5x (2762 / 1893 = 1.459)

Conclusions

Our 100 producers and 100 consumers, that communicate 10000 packets through a single channel, is the camel to go through the eye of a needle test case. Both π-WAM and SWI-Prolog can do it below a second using different means, but π-WAM beats SWI-Prolog here by a factor of ca. 1.5x.