I have a dilemma. A programming challenge if you w...

# multiplatform

[loke]

I have a dilemma. A programming challenge if you will. I'm starting to think what I'm trying to achieve is not actually possible.

In a nutshell: I'm developing a programming language interpreter in Kotlin. The technical details are not that interesting other than the fact that it has first-class symbols, similar to Lisp. Symbols live in a symbol table, which is just a hashmap, keyed on a string (the name of the symbol) and the value (the symbol object itself).

This is quite simple, but... If there are no more references to the symbol object, they are no longer useful. I can of course make the hashmap reference the underlying symbol using a WeakReference. However, once the reference is cleared, I need to remove the key from the hashmap.

In the Java backend, I can do this by leveraging ReferenceQueue and check when a reference has been dropped, and then remove the corresponding key (tracked in a separate hashmap).

But, I struggle to figure out a way to achieve this using the JS and Native backends. To be honest, I'm not sure these backends have the necessary infrastructure to make this possible. There certainly doesn't seem to be anything similar to ReferenceQueue. Using Cleaner is unfortunately not sufficient, since I can't change the code so that it works with wrapper objects. The thing that is returned from the namespace object has to be of type Symbol, not SymbolWrapper which includes a Cleaner.

[loke]

I've been thinking about this for a while, and I can't come up with a solution.

[streetsofboston]

Even when using WeakReferences, and other classes that depend on the JVM's garbage collector, you can't be sure that at any given time an object in no longer referenced. Your code using WeakReferences will be highly dependent on the underlying garbage collector. Your program will become a lot less deterministic.

You could create your own fully deterministic 'wrappers' with behavior and reference-counters that keep track on whether a the object being wrapped is still being 'referenced' (used) by your interpreter.

[loke]

@streetsofboston That's fine. I'm fully aware of the behaviour of the GC. In this case, what I'm actually trying to do is to prevent the symbol table from growing without bounds. It's just a hashmap that maps the name to a symbol object. However, once there are no more references to a symbol object, there is no need to keep it in the symbol table.

The issue I'm having is the cleanup of the symbol table. How can I detect that a symbol is no longer referenced anywhere so I can clean up the symbol table? In the JVM, this is easy by using a ReferenceQueue, but in Native, it seems that is not possible unless I add an extra field to the Symbol object (a reference to the Cleaner instance). But this is what I want to avoid, since I don't want to add extra fields to the Symbol object.

[CLOVIS]

I created a lib for that 😊
https://pedestal.opensavvy.dev/api-docs/weak/index.html

We have our own channel: #C078Z1QRHL3

[loke]

@CLOVIS my problem is that I want to create a map that weakly holds its values.

[loke]

In other words, once there are no refs to the object (other than in the map itself), the object (and corresponding key) should be removed.

[CLOVIS]

Ah sorry, I got that wrong, mine weakly holds by keys.

However, if you look at the implementation, you'll see the same idea can be applied to write a map that weakly holds its values; it's just an array of weak references that removes old values during iteration

[CLOVIS]

I could add it to the library but it would take a few days

[loke]

@CLOVIS yes, but that implementation is not ideal. Every time I look up an element in the map, it iterates over all the elements. This can be very costly in my case, since the map can get very large, and there are a lot of lookups.

[loke]

The ReferenceQueue implementation in the JVM is really ideal, and I'm not sure the other platforms are powerful enough to implement this.

[CLOVIS]

Then you could use a HashMap<K, WeakReference<T>> where get() only removes the current element if it's not valid anymore (instead of removing all the previous ones too). Maybe with a heuristic that every 1000 writes it does a full cleanup. That will lead to more memory usage, but it could be much faster.

[loke]

Hmm, yeah. I thought about that. The issue I'm having is that I want to protect against (perfectly valid) code in my interpreter which interns new symbols with unique names in a tight loop. Something like (pseudocode): for (i = 0...1000000) { internSymbol("name"+i) }

[loke]

There really is no way to avoid a full scan on Linux or JS?

[loke]

I was hoping there was some internal function I could use, something like a finaliser.

[CLOVIS]

There is a system similar to ReferenceQueue on JS. On Native, I'm not aware.

[loke]

Oh wait. Finalisers won't cut it.

[loke]

Because a symbol can be registered in more than one symbol table.

[loke]

What is the JS version called?

[CLOVIS]

I intend to support a multiplatform ReferenceQueue-like API in the future if I can make it work on all platforms, but I didn't get around to it yet

[CLOVIS]

https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/FinalizationRegistry

[loke]

Oh nice.

[loke]

That's exactly what I need.