4 ms·

This is mostly the real reason why interning gets used, to avoid long string comparisons over saving memory as such. Interned strings tend to not have a good c

by gopalv 2y ago

This is mostly the real reason why interning gets used, to avoid long string comparisons over saving memory as such. Interned strings tend to not have a good cleanup mechanism, in a system where a lot of them are churned through. So often they tend to actually use more memory as data patterns evolve in a system. I use the same trick when parsing json, where a large set of rows tend to have the keys repeated & the conversion to columnar is easier if the keys are interned.

kazinator 2y ago
In Lisp, interning is not only used for saving on string comparisons. It's the basis of the symbol abstraction. Or perhaps not the basis, but interning is the only way symbols can correspond to a printed representation. Without interning, we don't have it that A and A are the same object. A symbol being an object with a durable identity is important because it can have properties other than just the string which gives it a name.
o11c 2y ago
If your language supports good strong/weak references and containers thereof, cleaning up dead interned strings isn't hard. I'm not aware of any language that provides this out-of-the-box, unfortunately. Why do so many languages make weak references such second-class citizens? Why do all containers suck so much that you have to implement your own (and that's hoping the language is actually efficient enough to let you?)
- rscho 2y ago
  > not aware of any language that provides this out-of-the-box, unfortunately. Many lisps. Racket, for example.
- wongarsu 2y ago
  > I'm not aware of any language that provides this out-of-the-box, unfortunately The currently most prominent example would be Rust. Rc<T> is a simple generic container that implements reference counting, and any instance of it can be downgraded to a Weak<T>. Or Arc<T> and std::sync::Weak<T> if it needs to be thread safe.
  - o11c 2y ago
    I've done it in C++, so Rust is probably capable of it if you add enough layers of rc refcell and whatever else it requires to fit into its restricted worldview. Does Rust actually have container implementations that do all of the following: * When walking the container (either iterating or looking up, even through a non-mutable reference), call a user-provided predicate (not just builtin "weak" like many languages have via weakset/weakkeymap/weakvaluemap) to detect if a node should be considered "dead", and if so transparently remove the node. [In my experience this is relatively easy to add when you're implementing the container algorithms yourself, though I've never done it for bulk algorithms yet.] * When looking up a key (which may have different type or identity), the lookup returns the actual key the container had. [This may be impossible for container implementations that split the key.]
    - duped 2y ago
      To the first question, not really, and if it did it would be pretty fragile because of mutability requirements. It's fragile in C++ too because of iterator invalidation, Rust mostly turns that into a compiler error. To the second question, yes, it's super common.
      - o11c 2y ago
        I didn't have any problem with iterator/pointer invalidation (easy to merge into the same thing), since holding an active iterator inhibited expiration. It's possible to imagine an expiration system that doesn't automatically guarantee this but I didn't have one; the only non-weak-based expiry I had was based on timers, and it's sanest to only count time as elapsing at the heart of the event loop.
    - whytevuhuni 2y ago
      Mutating a container through a shared reference means the container either has to be single-threaded (not marked as Sync/Send), or be thread-safe. The single-threaded ones are easy to make, but Rust will prevent you from sending them to another thread, which is probably something you want. For thread-safe things, look into the crossbeam crate, it has really good collections. One I worked with was the dashmap, which has a .retain() method [1] that works over a shared map reference, but runs a closure which gets mutable access to each key and value, and decides whether to keep the pair or not. Its .get() [2] uses equality (so you can use a different object), but returns a reference to the original key-value pair. The .get_mut() will return it as mutable, but inside a guard that keeps the item locked until it goes out of scope. [1] https://docs.rs/dashmap/latest/dashmap/struct.DashMap.html#method.retain https://docs.rs/dashmap/latest/dashmap/struct.DashMap.html#m... [2] https://docs.rs/dashmap/latest/dashmap/struct.DashMap.html#method.get https://docs.rs/dashmap/latest/dashmap/struct.DashMap.html#m...
- jdougan 2y ago
  > not aware of any language that provides this out-of-the-box, unfortunately. Smalltalk has this. Class "Symbol".
- ayuhito 2y ago
  Go recently did add a new weak pointers and string interning package to its standard library which is an interesting read. [0] https://go.dev/blog/unique https://go.dev/blog/unique
  - ignoramous 2y ago
    > string interning package to its standard library TFA literally says interning isn't there in Go yet. While the unique package is useful, Make is admittedly not quite like Intern for strings, since the Handle[T] is required to keep a string from being deleted from the internal map. This means you need to modify your code to retain handles as well as strings. > an interesting read Tailscale's attempt at implementing "unique" was quite... something: https://tailscale.com/blog/netaddr-new-ip-type-for-go https://tailscale.com/blog/netaddr-new-ip-type-for-go
    - ayuhito 2y ago
      The Tailscale article taught me a lot! Thanks for sharing.
- igouy 2y ago
  WeakArray? Ephemerons? 1997 "Ephemerons: A New Finalization Mechanism" https://dl.acm.org/doi/pdf/10.1145/263698.263733 https://dl.acm.org/doi/pdf/10.1145/263698.263733 "Linked weak reference arrays: A hybrid approach to efficient bulk finalization" https://www.sciencedirect.com/science/article/pii/S0167642320300897 https://www.sciencedirect.com/science/article/pii/S016764232...
- crabbone 2y ago
  > not aware of any language that provides this out-of-the-box, unfortunately. ActionScript 3 had it :D

by gopalv 2y ago

kazinator 2y ago

In Lisp, interning is not only used for saving on string comparisons. It's the basis of the symbol abstraction. Or perhaps not the basis, but interning is the only way symbols can correspond to a printed representation. Without interning, we don't have it that A and A are the same object. A symbol being an object with a durable identity is important because it can have properties other than just the string which gives it a name.

o11c 2y ago

If your language supports good strong/weak references and containers thereof, cleaning up dead interned strings isn't hard. I'm not aware of any language that provides this out-of-the-box, unfortunately. Why do so many languages make weak references such second-class citizens? Why do all containers suck so much that you have to implement your own (and that's hoping the language is actually efficient enough to let you?)

rscho 2y ago
> not aware of any language that provides this out-of-the-box, unfortunately. Many lisps. Racket, for example.
wongarsu 2y ago
> I'm not aware of any language that provides this out-of-the-box, unfortunately The currently most prominent example would be Rust. Rc<T> is a simple generic container that implements reference counting, and any instance of it can be downgraded to a Weak<T>. Or Arc<T> and std::sync::Weak<T> if it needs to be thread safe.
- o11c 2y ago
  I've done it in C++, so Rust is probably capable of it if you add enough layers of rc refcell and whatever else it requires to fit into its restricted worldview. Does Rust actually have container implementations that do all of the following: * When walking the container (either iterating or looking up, even through a non-mutable reference), call a user-provided predicate (not just builtin "weak" like many languages have via weakset/weakkeymap/weakvaluemap) to detect if a node should be considered "dead", and if so transparently remove the node. [In my experience this is relatively easy to add when you're implementing the container algorithms yourself, though I've never done it for bulk algorithms yet.] * When looking up a key (which may have different type or identity), the lookup returns the actual key the container had. [This may be impossible for container implementations that split the key.]
  - duped 2y ago
    To the first question, not really, and if it did it would be pretty fragile because of mutability requirements. It's fragile in C++ too because of iterator invalidation, Rust mostly turns that into a compiler error. To the second question, yes, it's super common.
    - o11c 2y ago
      I didn't have any problem with iterator/pointer invalidation (easy to merge into the same thing), since holding an active iterator inhibited expiration. It's possible to imagine an expiration system that doesn't automatically guarantee this but I didn't have one; the only non-weak-based expiry I had was based on timers, and it's sanest to only count time as elapsing at the heart of the event loop.
  - whytevuhuni 2y ago
    Mutating a container through a shared reference means the container either has to be single-threaded (not marked as Sync/Send), or be thread-safe. The single-threaded ones are easy to make, but Rust will prevent you from sending them to another thread, which is probably something you want. For thread-safe things, look into the crossbeam crate, it has really good collections. One I worked with was the dashmap, which has a .retain() method [1] that works over a shared map reference, but runs a closure which gets mutable access to each key and value, and decides whether to keep the pair or not. Its .get() [2] uses equality (so you can use a different object), but returns a reference to the original key-value pair. The .get_mut() will return it as mutable, but inside a guard that keeps the item locked until it goes out of scope. [1] https://docs.rs/dashmap/latest/dashmap/struct.DashMap.html#method.retain https://docs.rs/dashmap/latest/dashmap/struct.DashMap.html#m... [2] https://docs.rs/dashmap/latest/dashmap/struct.DashMap.html#method.get https://docs.rs/dashmap/latest/dashmap/struct.DashMap.html#m...
jdougan 2y ago
> not aware of any language that provides this out-of-the-box, unfortunately. Smalltalk has this. Class "Symbol".
ayuhito 2y ago
Go recently did add a new weak pointers and string interning package to its standard library which is an interesting read. [0] https://go.dev/blog/unique https://go.dev/blog/unique
- ignoramous 2y ago
  > string interning package to its standard library TFA literally says interning isn't there in Go yet. While the unique package is useful, Make is admittedly not quite like Intern for strings, since the Handle[T] is required to keep a string from being deleted from the internal map. This means you need to modify your code to retain handles as well as strings. > an interesting read Tailscale's attempt at implementing "unique" was quite... something: https://tailscale.com/blog/netaddr-new-ip-type-for-go https://tailscale.com/blog/netaddr-new-ip-type-for-go
  - ayuhito 2y ago
    The Tailscale article taught me a lot! Thanks for sharing.
igouy 2y ago
WeakArray? Ephemerons? 1997 "Ephemerons: A New Finalization Mechanism" https://dl.acm.org/doi/pdf/10.1145/263698.263733 https://dl.acm.org/doi/pdf/10.1145/263698.263733 "Linked weak reference arrays: A hybrid approach to efficient bulk finalization" https://www.sciencedirect.com/science/article/pii/S0167642320300897 https://www.sciencedirect.com/science/article/pii/S016764232...
crabbone 2y ago
> not aware of any language that provides this out-of-the-box, unfortunately. ActionScript 3 had it :D