# Reference String Based on Instance?
**URL:** https://discourse.julialang.org/t/reference-string-based-on-instance/9368
**Category:** Internals & Design
**Created:** [February 27, 2018, 3:48pm UTC](https://discourse.julialang.org/t/reference-string-based-on-instance/9368 "2018-02-27T15:48:04Z")
**Posts on this page:** 6
**Page:** 1
### Author:  [@RandomString123](https://discourse.julialang.org/u/RandomString123)
#### Post date: [February 27, 2018, 3:48pm UTC](https://discourse.julialang.org/t/reference-string-based-on-instance/9368/1 "2018-02-27T15:48:04Z")
I was looking over the TextParse package and I was surprised to find custom code in this file [https://github.com/JuliaComputing/TextParse.jl/blob/master/src/util.jl](https://github.com/JuliaComputing/TextParse.jl/blob/master/src/util.jl) and function `nonallocating_setindex!` that keeps a list of strings around and indexes to them when a string is allocated.
This made me wonder, since this PR means that strings should “technically” be immutable [https://github.com/JuliaLang/julia/issues/22193](https://github.com/JuliaLang/julia/issues/22193), does the base string type automatically detect if there is an existing reference to a string and if there is just return that reference? If not isn’t this something that should be added? It seems pretty common among garbage collected languages with immutable strings.
---
### Author:  [@StefanKarpinski](https://discourse.julialang.org/u/StefanKarpinski)
#### Post date: [February 27, 2018, 5:27pm UTC](https://discourse.julialang.org/t/reference-string-based-on-instance/9368/2 "2018-02-27T17:27:51Z")
Immutability means that I could be done as an optimization. It is not currently done, however. How detect pre-existence of another reference efficiently?
---
### Author:  [@RandomString123](https://discourse.julialang.org/u/RandomString123)
#### Post date: [February 27, 2018, 5:48pm UTC](https://discourse.julialang.org/t/reference-string-based-on-instance/9368/3 "2018-02-27T17:48:21Z")
I think the naive solution would just a dictionary or set implementation. A faster and probably more memory efficient structure would be a Trie. My specialty is not in memory allocators and garbage collection so I can’t say for sure.
Also, as where string interning is efficient memory wise there are typically trade-offs, one being the expense of the interning operation. [String interning - Wikipedia](https://en.wikipedia.org/wiki/String_interning) suggests that Julia already interns symbols. Perhaps that system could be built on top of?
In all cases I think having the functionality available but perhaps not used by default would help greatly and would remove the necessity for every package that is string heavy to implement its own, usually not inter-operable, string interning mechanism.
---
### Author:  [@StefanKarpinski](https://discourse.julialang.org/u/StefanKarpinski)
#### Post date: [February 27, 2018, 7:13pm UTC](https://discourse.julialang.org/t/reference-string-based-on-instance/9368/4 "2018-02-27T19:13:00Z")
At what point would you do the dictionary lookup? Any time a string object is created? That would be quite expensive. Interned objects like symbols are never garbage collected so interning all strings unconditionally would mean that we never free the storage for any string object which would be fairly impractical.
There is a package that provides an opt-in interned string type:
> [@\[ANN\] InternedStrings.jl: Allocate strings once and reuse them](https://discourse.julialang.org/t/ann-internedstrings-jl-allocate-strings-once-and-reuse-them/7344):
>
> This has been bothering me since I first started using julia 3 years ago. Julia has immutable strings, that are not interned. Late at night about a week ago I worked out how to solve it. Its not actually that hard. This package solves that, and it does so without breaking garbage collection. The full explanation and motivational rant is in the readme. [https://github.com/oxinabox/InternedStrings.jl](https://github.com/oxinabox/InternedStrings.jl) If someone wants to check the math there, and make a PR, I’ld appreciate it. My math says t…
> **[GitHub - JuliaString/InternedStrings.jl: Fully transparent string interning...](https://github.com/JuliaString/InternedStrings.jl)**
>
> Fully transparent string interning functionality, with proper garbage collection - GitHub - JuliaString/InternedStrings.jl: Fully transparent string interning functionality, with proper garbage col...
One possibility would be to automatically intern all sufficiently short strings. However, since a pointer to such an interned string is already 16 bytes on most systems, that solution is strictly dominated by storing short (\< 16-byte) strings inline. I mentioned that [previously](https://discourse.julialang.org/t/progress-towards-faster-sortperm-for-strings/8505/4) which led @xiaodai to prototype the idea here:
> **[GitHub - JuliaString/ShortStrings.jl: A fast implementation of short strings...](https://github.com/JuliaString/ShortStrings.jl)**
>
> A fast implementation of short strings of fixed size. Great for sorting and group-by operations - GitHub - JuliaString/ShortStrings.jl: A fast implementation of short strings of fixed size. Great f...
---
### Author:  [@RandomString123](https://discourse.julialang.org/u/RandomString123)
#### Post date: [February 28, 2018, 2:19pm UTC](https://discourse.julialang.org/t/reference-string-based-on-instance/9368/5 "2018-02-28T14:19:25Z")
I will look into adopting these packages. It would be nice if the community would decide to back one of the solutions at some point before 1.0 to stop fragmentation of implementations.
---
### Author:  [@oxinabox](https://discourse.julialang.org/u/oxinabox)
#### Post date: [March 6, 2018, 2:36am UTC](https://discourse.julialang.org/t/reference-string-based-on-instance/9368/6 "2018-03-06T02:36:44Z")
> [@RandomString123](#):
>
> A faster and probably more memory efficient structure would be a Trie. My specialty is not in memory allocators and garbage collection so I can’t say for sure.
A trie would be slower, (you have to re-stitch all the characters into a string, everytime you operate with it, unless you fully re-implement all string operations, then maybe only C interop and a few other things would be slow).
But probably more memory efficient. (at least once you have a lot of strings interned)
Particularly, if we had compresses tries.