Stream implementation

[LaurensRietveld]

Have you every considered a stream implementation, instead of a callback? Any interest in that direction?

[RubenVerborgh]

Node streams for objects come with a terrible performance bottleneck (see for instance rdfjs/N3.js#6), but iteration by itself would makes sense. However, there is a performance penalty associated with crossing the JS/C++ barrier, so the current system of limit/offset is probably as efficient as it gets.

[RubenVerborgh]

…but it would make sense to implement a JavaScript-land iterator interface on top of the limit/offset system, for instance such that triples are fetched in groups of 100.

[LaurensRietveld]

Interesting discussion there, haven't had such a horrible experience with streams myself. Things probably changed quite a bit in node-js land since that discussion. I reran your perf script on a file of mine, and these are the results:

The N3 parser perf scripts in master (uses N3.Parser):

$ node N3Parser-perf.js input.nt
- Parsing file /home/lrd900/triply/N3.js/perf/input.nt: 48275.659ms
* Triples parsed: 25650502
* Memory usage: 64MB

A script I quickly wrote that uses fs.createReadStream(filename).pipe(N3.StreamParser({documentIRI: base})):

$ node N3Parser-stream-perf.js input.nt
- Parsing file /home/lrd900/triply/N3.js/perf/input.nt: 54330.664ms
* Triples parsed: 25650502
* Memory usage: 63MB

Ran on node v7.7.2.

Ps. an iterator would be great to have as well of course ;)

[RubenVerborgh]

Not bad, not bad at all… I wonder how much better RubenVerborgh/AsyncIterator performs on that.
Native iterators are to be tested as well, definitely.

In any case, a more than appropriate feature request.

[LaurensRietveld]

What would you think about the implementation details ruben? I was thinking about:

• Adding a pause and resume function to the c code, that stops/resumes the iterator.
• Sending each statement via a callback to nodejs
• Glue everything together in either a stream and/or something like an async iterator on the JS side.

Any thoughts?

[RubenVerborgh]

Adding a pause and resume function to the c code, that stops/resumes the iterator.
Sending each statement via a callback to nodejs

I wouldn't do that, you want to reduce the number of times you cross the C/JavaScript barrier for performance reasons.

Glue everything together in either a stream and/or something like an async iterator on the JS side.

I would implement all of this in JS-land, with a stream/iterator that communicates with the C code in batches of N triples (with N for instance 100).

[LaurensRietveld]

I've already implemented a stream-wrapper as you describe myself, and notice a performance penalty there as well (i.e., fetching 1000 query results is cheaper than fetching 10x100 query results).
Guess we have to quantify the performance cost of both approaches, I'll see whether I can cook something up

[RubenVerborgh]

We probably should have an optional bufferSize parameter with a sensible default. Maybe 1024 or so is more sensible than 100 (but for TPF I'd like to set it to 100 explicitly to avoid unneeded work).

Also note optimizations such as this one that minimize the number of JavaScript objects being allocated. If multiple triples in the same batch share the same subject (or predicate or object), then they will be the exact same in-memory string. We should carefully think about these as well.

[LaurensRietveld]

A quick experiment where I 1) fetch 1 million query results in 1 go (i.e. 1 million results in single callback), and 2) fetch 1 million results in batches of 100 (i.e. 10.000 results per callback):

$ node test 1
fetching 1000000 query results in 1 loops
done: 1377.444ms

$ node test 100
fetching 1000000 query results in 100 loops
done: 5852.993ms

The difference in performance greatly depends on the query. A null, null,null query performance only has a small performance penalty when divided over multiple callbacks. The above result is from a null, <p>. null query.
There seems to be a performance penalty with an offset. Querying a single triple (with a bound predicate in the query) is a lot (100x) slower with an offset of 1000000 compared to an offset of 1.

To me, it seems that implementing this in batches (all on the js side) comes at a cost.
A middleground would be to still implement the pause / resume functionality in the c++ code (which should avoid calculating the offset for each chunk), while still sending the results in bulk (indeed something like 1024 sounds sensible). That way, we'd still be able to use your optimization as well to some extent.

[RubenVerborgh]

To me, it seems that implementing this in batches (all on the js side) comes at a cost.

Yes, but everything depends on the access pattern! What if only the first 10 results are ever used?

For the scenario where we know that a) all triples will be read and b) they all fit in memory, my assumption would indeed be that fetching all is more performant.

Can you try with different buffer sizes to see the effect? I'm thinking that around 1024 is a sensible default. Note that we could incrementally adapt the buffer size etc.

[RubenVerborgh]

Also, the ?s <p> ?o pattern is a very exotic one, you won't see it in a lot of SPARQL queries (and if you do, it is unlikely to be the first to be resolved).

[LaurensRietveld]

Yes, but everything depends on the access pattern! What if only the first 10 results are ever used?

Agreed, it depends on the access pattern. What is your usecase only fetching the first 10 results? If you know you're interested in 10, you can just use the callback mechanism and add a limit of 10 right? In a stream scenario you're often interested in all the results (but without the memory costs of course).

For the scenario where we know that a) all triples will be read and b) they all fit in memory, my assumption would indeed be that fetching all is more performant.

It's b) that I'd like to fix here with a stream implementation. Maybe I wasn't clear, but I think we can get the best of both worlds (low memory usage and fast result streaming) by:

• Adding a pause/resume function to the c++ code
• Sending results to js in batches in size bufferSize (with optionally a dynamic buffer / batch size)
• Making a stream implemention in JS that pauses/resumes the iterator function in C++ to avoid backpressure.

Can you try with different buffer sizes to see the effect? I'm thinking that around 1024 is a sensible default. Note that we could incrementally adapt the buffer size etc.

That would only get worse right? My example was 1 million triples divided over 100 chunks, i.e. a buffer size of 10.000. Lowering that even more would greatly degrade performance (takes ~50 seconds). Or is there something lost in translation here? ;)

Also, the ?s <p> ?o is a very exotic one.

True, with ?s ?p <o> we get a smaller effect, but still quite large:

$ node test 1
fetching 1000000 query results in 1 loops
done: 2124.442ms

$ node test 100
fetching 1000000 query results in 100 loops
done: 1401.727ms

[RubenVerborgh]

What is your usecase only fetching the first 10 results? If you know you're interested in 10, you can just use the callback mechanism and add a limit of 10 right? In a stream scenario you're often interested in all the results (but without the memory costs of course).

Nah, a stream means that I can stop whenever I want. Maybe the 10th result has a characteristic that I'm interested in. Maybe my downstream stops pulling after 10 results. In general, a consumer does not always know in advance how many results to pull.

It's b) that I'd like to fix here with a stream implementation. Maybe I wasn't clear, but I think we can get the best of both worlds (low memory usage and fast result streaming) by:

Adding a pause/resume function to the c++ code

That means maintaining state though, and carefully cleaning up. You should especially be careful with keeping JavaScript objects alive (such as the strings I mentioned above as an optimization).

Making a stream implemention in JS that pauses/resumes the iterator function in C++ to avoid backpressure.

Indeed, avoiding backpressure is key here; but backpressure also exists when I'm slowly pulling 10 results and thousands are already in memory.

That would only get worse right? My example was 1 million triples divided over 100 chunks, i.e. a buffer size of 10.000.

My bad, I misread. Serious performance penalty indeed. I'm surprised offsetting is not cheaper. Are we sure the problem is offsetting BTW? What is the overhead of 100 times fetching the first 10.000 results versus fetching 100 consecutive pages of 10.000 results?

True, with ?s ?p we get a smaller effect, but still quite large:

Wait, isn't that result better?

[LaurensRietveld]

Nah, a stream means that I can stop whenever I want. Maybe the 10th result has a characteristic that I'm interested in. Maybe my downstream stops pulling after 10 results. In general, a consumer does not always know in advance how many results to pull.

Fair enough. Still, we can simply optimize the buffer size in that case. A buffer size of 1024 still sounds reasonable, as the performance difference in fetching 10 or 1024 is negligible. Ideally, with a dynamic buffer this can be improved.

That means maintaining state though, and carefully cleaning up. You should especially be careful with keeping JavaScript objects alive (such as the strings I mentioned above as an optimization).

Good points

Indeed, avoiding backpressure is key here; but backpressure also exists when I'm slowly pulling 10 results and thousands are already in memory.

That's right, but guess we have to find a middle-ground between memory usage and performance here. And a buffer of 1024 still sounds reasonable right?

My bad, I misread. Serious performance penalty indeed. I'm surprised offsetting is not cheaper. Are we sure the problem is offsetting BTW? What is the overhead of 100 times fetching the first 10.000 results versus fetching 100 consecutive pages of 10.000 results?

Good point. The results are 1) 950ms for fetching the first 10.000 results for 100 times, vs. 2) 5.7 seconds for fetching 100 consecutive pages of 10.000 results. (using the <p> query here).

Wait, isn't that result better?

Ha! Completely misread, you're right. No clue why a chunked query would perform better than a single large query. You got any ideas?