Persistent Data Structures for Objective-C | Hacker News Reader

Persistent Data Structures for Objective-C

github.com

18 pointsastashov7 comments

Objective-C data structures are already immutable by default. What do these persistent data structures bring to the table that the default immutable NSDictionary, NSArray, NSSet, etc., don't?

Persistent data structures utilize structural sharing, meaning that the current version of the structures shares as much from its tree as possible with old versions. This effectively allows any thread to make a new version of the data structure efficiently and without having to use locks for reading. They are very useful in the face of concurrency and multiple reader/writer threads.

One thing to remember is that getting a new version of the data structure does not change old ones at all. In order to change state, in Clojure for example, you use constructs such as atoms to "advance" a persistent data structure forward. Think about it like advancing through your git commit history - efficiently and by only applying the delta for the next "change".

They are immutable by default, but it's expensive to get a new data structure with some changes in it. That's what persistent data structures for. I personally like this explanation - https://github.com/vacuumlabs/persistent#what-are-persistent...

Expensive how?

Your classes are 10-20x slower in every other way, which definitely would offset any imaginary expense you think calling `mutableCopy` costs.

I have to tell you in 10+ years of writing Objective-C where I was like [myArray mutableCopy] is super slow, I need a replacement. I've wished for an NSOrderedDictionary though.

10-20x slower means it makes sense to use a persistent map when the size of your Dictionary is > 20 records.

Then,

  // yourDictionary is NSMutableDictionary, [yourDictionary count] > 20
  NSMutableDictionary *mutable = [yourDictionary mutableCopy];
  mutable[@"old_key"] = @"new_value";
  NSDictionary *changedDict = [NSDictionary dictionaryWithDictionary:mutable];

will be slower than

  // yourDictionary is AAPersistentHashMap, [yourDictionary count] > 20
  AAPersistentHashMap *changedDict = [yourDictionary setObject:@"new_value" forKey:@"old_key"];

Remember, you need to get another immutable map, which is a modified version of the original, preferably memory-efficient, which means we want to reuse the unchanged keys/values of the original map.

Does anybody know if there is anything similar for golang?

The underlying datastructure is a Hash Array Mapped Trie. Searching for "golang hamt" and "golang immutable" turns up a number of results but I didn't look into any of them but they're generally clones of Clojure's version.

Reply on news.ycombinator.com