Rope strings

[laishere]

It's great to see @bellard is back!

What makes me most excited about is the commit on long strings concatenation:
bellard/quickjs@156d981

I tested on the latest quickjs and quickjs-ng with qjs:

const t1 = Date.now()
let str = '';
for (let i = 0; i < 1000_000; i++) {
  str += 'a';
}
const t2 = Date.now()
console.log(t2 - t1);

quickjs-ng: 6854ms
quickjs: 112ms

Do we have any plan to merge this commit? @saghul @bnoordhuis

[bnoordhuis]

I've seen that commit but I'm not sold on the balancing logic. The V8 people probably sunk more man hours in optimizing strings than went into quickjs in total, and it doesn't do that, it flattens the rope into a linear string whenever it performs an operation that isn't concatenation.

Cons strings (ropes) are also a bit of a double-edged sword because they make it easy to hit out-of-memory conditions. Build up a big string, try to do something with it, boom, out of memory because you need 2x the memory when flattening. It's one of those evergreen footguns for Node.js newbies.

The array-as-string-builder pattern is (and always will be) more memory efficient and (way!) faster than ropes/cons strings. IMO it's better to steer users in that direction:

let str = new Array(1000_000)
for (let i = 0; i < 1000_000; i++) {
  str[i] = 'a';
}
str = str.join("")
// finishes in milliseconds flat

[laishere]

Thank you for your opinions!

I don't know much about the rope data struct yet. But I think we do need a general way to process the strings more efficiently.
Because I think it's not practical to apply this array optimization on the various exisiting JS libraries.

I have an experience on using cheerio to parse the HTML with quickjs, it's extremely slow on some big HTML files. I think it has something to do with the slow string operations like slicing and concatenation. But I didn't verify it. At the end, I have to switch to libxml2 which cost much effort to implement but of course better results.

Now we have to deal with O(n) complexity even if we want to append a newline to the end of the string. And string operations are heavily used.

If we can trade extra O(n) memory for improved time efficiency (2x for like 60x), I think it's a worthwhile compromise, since modern devices typically have sufficient memory. And less time means faster response + lower CPU energy cost.

And I think we already need 2x memory when concat two strings. Because it's not possible to apply the in place concatenation for normal str1 = str1 + str2 even let str3 = str1 + str2 operations with current implementation.

I think at least we should make it an optional feature that we can turn on if we need it.

[laishere]

Just ran a simple cheerio test on quickjs and quickjs-ng, suprisingly, it's almost the same:
quickjs: 1118ms
quickjs-ng: 1115 ms

I was wrong about the slow HTML parsing is caused by the current string implementation.

[bnoordhuis]

@saghul wdyt, is this something we want to port over or not? I'm leaning towards 'no' myself.

[bnoordhuis]

I'm going to make the call that we're not adding cons strings for now; ergo, closing.

[saghul]

Sorry for the belated reply. I trust your judgement here 👍

[bnoordhuis]

bellard/quickjs#445 (comment) mentions rope strings help in at least one real-world use case. Reopening.

[ahaoboy]

https://github.com/ahaoboy/js-engine-rope-strings-test

I tested the following simple code. Both llrt and txiki.js use the qjs-ng engine, but the performance is almost ten times faster. This may be due to the different memory allocators used.

var str = '';
for (var i = 0; i < N; i++) {
  str += 'a';
}

ubuntu

Engine	array	loop
bun	1	2
node	2	8
deno	2	8
graaljs	30	29
hermes
llrt	8	128
txiki.js	9	112
quickjs	10	13
quickjs-ng	11	1966
mujs	27	899
mujs-pgo	22	916
mujs-one
xst
JavaScriptCore
v8	3	7
spidermonkey	2	4
JerryScript
primjs	9	12
rquickjs	12	156
rquickjs-pgo	12	155
ChakraCore	3	7
duktape	32	1741
nova
boa	109	240
engine262	[object Object]	[object Object]
ladybird	10	10
goja
kiesel	108	3152
mozjs
jint	89	62
dune	�[33m3�[0m	�[33m8�[0m
jjs
rhino
njs	4	1910
ringo	145	68
lo	2	6
spiderfire	1	5
hako
quickjs-emscripten	55	1854

[Icemic]

I tried @ahaoboy 's test too, and it is weird...

Since I don't have a handy compiling env, I downloaded the binary (qjs-windows-x86_64.exe) from release v0.10.1. (btw, maybe a new release is needed?)
As a comparison, I use my self-made binding quickjs-rusty using the same version of code.

My machine is AMD 5600X and Windows 11.

quickjs-ng v0.10.1
array 10
loop 323

my binding:
array 12
loop 98

my another project using my binding (using latest quickjs-ng):
array 10
loop 93

nodejs v22.20.0:
array 2
loop 5

I tried to enable or disable mimalloc but it seems not to have a notable impact.
However, in my many test runs of my own binding, there were occasional results which approached those of qjs.exe (loop > 300).
So I think this may be a compiler optimization or CPU scheduling issue? Should we try on a PGO version?