Immutable collections are extremely slow

[gabbard]

Issue by rgabbard
Friday Jun 01, 2018 at 19:13 GMT
Originally opened as https://github.com/isi-nlp/isi-flexnlp/issues/349

---

Timings for immutable set creation:

empty frozen: base 0.0005451000106404535 ms vs probe 0.0016776999473222531 ms 
singleton frozen: base 0.000693500078341458 ms vs probe 0.0019225999494665302 ms 
non singleton frozen: base 0.0007623999408679083 ms vs probe 0.0021223000658210367 ms 
big set frozen: base 1.3013469000725308 ms vs probe 1.9578501000069082 ms 

empty immutable: base 0.0006041000233381055 ms vs probe 0.21783060001325794 ms 
singleton immutable: base 0.000735200046619866 ms vs probe 0.42865529994742246 ms 
non singleton immutable: base 0.0008420000085607171 ms vs probe 0.44097009995311964 ms 
big set immutable: base 1.2643873998968047 ms vs probe 100.92103900005895 ms 

vs” numbers are “time for creation of the list used for initialization” vs “time for creation of the set”.
top numbers are frozenset bottom numbers are immutableset
We are 50-200 times slower :-(

(this is for just object creation)

[gabbard]

Comment by rgabbard
Friday Jun 01, 2018 at 19:15 GMT

---

A native implementation may be in order. I wonder if we could just steal the frozenset implementation from https://github.com/python/cpython/blob/491bbedc209fea314a04cb3015da68fb0aa63238/Objects/setobject.c and remove all mutating methods

@ConstantineLignos

[gabbard]

Comment by ConstantineLignos
Friday Jun 01, 2018 at 19:31 GMT

---

We certainly could go the C route. I'm less worried about the implementation time than the time required to sort out distribution for all platforms (which will possibly have to kept up for every new minor Python version). It may be more maintainable to do it in Cython. I have to run something for a while later tonight. If I still have energy left at that point, I might try do see how far I can get in doing a version of ImmutableSet in Cython and seeing how much faster it is.

[gabbard]

Comment by ConstantineLignos
Friday Jun 01, 2018 at 19:35 GMT

---

Digging in a little bit more, there probably won't be a difference between C and Cython for distribution; we're going to have to get into the business of building wheels either way. There are some solutions out there that can automatically build wheels for all Python platforms. Cython is less of a commitment (and is much more readable than a pure C extension) so I'd still like to give it a try first.

[gabbard]

Comment by rgabbard
Friday Jun 01, 2018 at 19:47 GMT

---

Trying Cython first sounds fine to me

[gabbard]

Pursuing this seriously will require benchmarks: #17 #16 #15 #14