Add WeakRef Implementation

LanderlYoung commented 3 months ago

Description is continuously edited according to discussions.

This PR did several related things.

1. Refactor JSObject weak reference list to support different kinds of weak reference

Changed JSObject.u.first_weak_ref, which was designed for WeakMap/WeakSet only. Also added weak reference support to JSString (ie. Atom/Symbol ).

It makes it easy to add WeakRef implementation. (And possibly FinalizationRegistry which is almost done, will create another PR after this one ).

2. Add WeakRef implementation

Added standard WeakRef implementation together with test cases. Referenced to https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/WeakRef

3. Support Symbol as WeakMap key

As a nice-to-have thing, also closed a TODO item in the doc.

https://github.com/bellard/quickjs/blob/6e2e68fd0896957f92eb6c242a2e048c1ef3cae0/doc/quickjs.texi#L286

4. Change JSObject.weak_ref_list to use a bit and external hash table.

Save memory for each JSObject (8 bytes on 64-bit platform, 4 bytes on 32-bit platform), while still maintaining good performance.

Performance test result

Test Code

```JavaScript var size = 1000 * 1000; var start = Date.now(); var objs = new Array(size); var weak1 = new Array(size); var weak2 = new Array(size); var newObject = time (() => { for (var i = 0; i < size; i++) { objs[i] = { index: i }; } }); var newWeak1 = time(() => { for (var i = 0; i < size; i++) { weak1[i] = new WeakRef(objs[i]); } }); var newWeak2 = time(() => { for (var i = 0; i < size; i++) { weak2[i] = new WeakRef(objs[i]); } }); var deref1 = time(() => { for (var i = 0; i < size; i++) { assert(weak1[i].deref(), objs[i]); assert(weak2[i].deref(), objs[i]); } }); var free1 = time(() => { for (var i = 0; i < size / 2; i++) { objs[i] = undefined; } }); var deref2 = time(() => { for (var i = 0; i < size / 2; i++) { assert(weak1[i].deref(), undefined); assert(weak2[i].deref(), undefined); } }); var free2 = time(() => { weak1 = undefined; weak2 = undefined; objs = undefined; }); var total = Date.now() - start; ```

Test Result: (tested on Macbook Pro with M2 Pro chip, with 1 million iterations, time-unit is millisecond)

code branch	newObject	newWeak1	newWeak2	deref1	deref2	free1	free2	total
pointer in JSObject	169	107	195	1064	514	53	131	2233
w/ hashmap	64	255	324	1078	541	126	181	2568

pointer in JSObject: use JSObject.first_weakref pointer
w/ hashmap: use a bit flag in JSObject.has_weak_ref and a JSRuntime.weak_target_map

New Object operations are faster, maybe due to a smaller object size.
New WeakRef operations are slower, but still acceptable.
Free object (that are weakly referenced) operations take slightly longer, less than 100 ns per operation.

Furthermore, theoretically, Objects/Symbols that are not weakly referenced have no performance impact.

Also added a generic (good performance) hash map implementation. I tried to refactor JS Map based on that which resulted in a good performance improvement (https://github.com/LanderlYoung/quickjs/pull/4).

Follow ups

other commits based on this PR:

Ready to open other PRs once this PR is merged.

BTW: very happy to see QuickJs is accepting PRs I'm the author of ScriptX, and I added implementations of WeaRef with the help of WeakMap to meet project needs, while not fulfilling the ES standard. When I notice QuickJS is accepting PRs, I feel it's time to contribute some code!

saghul commented 3 months ago

FWIW:

https://github.com/quickjs-ng/quickjs/pull/58 https://github.com/quickjs-ng/quickjs/pull/148 https://github.com/quickjs-ng/quickjs/pull/168

LanderlYoung commented 3 months ago

FWIW:

quickjs-ng/quickjs#58 quickjs-ng/quickjs#148 quickjs-ng/quickjs#168

@saghul Thanks for the info.

This PR focused more on generic implementation.

Instead of using JSMapRecord for a weak ref record, using it for WeaRef, which I also did for a quick implementation, this PR did add a generic JSWeakRecord and related basic functions, and adaptedJSMapRecord accordingly.

Also the JSWeakRecord is used to implementation FinalizationRegistry.

LanderlYoung commented 3 months ago

Based on the PR, I am doing other commit. Since each of them has a fairly considerable amount of code, I'm going to separate them into three PRs.

Looking forward to the code review, and I'd like to fix any comment ASAP ;)

Follow ups:

https://github.com/LanderlYoung/quickjs/pull/3 also closed a TODO item https://github.com/bellard/quickjs/blob/6e2e68fd0896957f92eb6c242a2e048c1ef3cae0/TODO#L50
https://github.com/LanderlYoung/quickjs/pull/2
IMPLEMENTATION DETAIL:
- It is hard to call a js function when Object is freed, while still respect to the principle that one can't touch js context in finalization.
- In order to implement that, we shcedule a job (with JS_EnqueueJob) to perform callback when an Object is GCed.

saghul commented 3 months ago

I have not reviewed it, I was just pointing out that there is prior art.

We do have the intention to merge both projects but at this stage I wouldn't necessarily pick a new implementation but take the existing one and improve where necessary.

Just my 2 cents.

bellard commented 3 months ago

Note that I did not merge the quickjs-ng WeakRef implementation because it adds a pointer in each JSString which adds too much memory overhead IMHO. This implementation is not better on this topic.

Ideally, the "first_weak_ref" pointer in JSObject should also be removed. My idea was to add a bit in JSString/JSObject telling that they may be pointed by a weak reference. Another structure (a hash table) would be added to find the weak reference when the JSString or JSObject is freed. With this solution, the added memory is proportional to the number of values pointed by weak references instead of being proportional to the number of JSObject/JSString. There is a small added cost in case a JSObject/JSString pointed by a weak reference is freed, but I doubt it is critical.

LanderlYoung commented 3 months ago

@bellard Thanks for the reply.

I understand your thoughts and did notice the TODO item in the project. I've already done that, but haven't merged the commit into this PR. It is now in my forked repo

https://github.com/LanderlYoung/quickjs/pull/3 also closed a TODO item https://github.com/bellard/quickjs/blob/6e2e68fd0896957f92eb6c242a2e048c1ef3cae0/TODO#L50

I'd like to merge the commit into this PR.

UPDATE: The commit has been merged into this PR.

Questions

Before that commit merges into this PR, there are two questions to be determined.

1. What does this comment mean, at the bottom of JSObject struct?

/* byte sizes: 40/48/72 */

By my guess, the 40/x/72 means sizeof(JSObject) on 32-bit and 64-bit platforms. We have successfully removed a pointer from the struct, that should be updated to 36/x/64.

But what does the 48 mean?

2. A generic hash-map implementation is added, which takes around 200 lines of code. I investigated current hash-map implementations, JSAtomStruct JSShape JSMapState all have an "inline" implementation of hash-map, but can not directly be reused.

So a new one is added, but it is similar to JSMapState's one, which is a little duplicated IMHO. Maybe we can refactor JSMapState to be based on the new generic one.

But it's up to the maintainers' decision, and I'd like to commit changes based on that.

LanderlYoung commented 2 months ago

gentle ping 🌹 @bellard @chqrlie

There is lots of code. Please comment as I'd like to optimize it.

bellard / quickjs