seems like add isn't O(1)

[uriva]

x = [random.randint(0, 1000000) for _ in range(1000000)]
ps = pyrsistent.s(*x)
for i in range(10): ps2 = ps.add(1)

last line takes around 4s.

In immutables (https://github.com/MagicStack/immutables) the same action is immediate (but they don't have a set and list apis).

Similarly, update is slow even for a list with a few elements.

[tobgu]

Thanks for reporting this! Sorry for not getting back to you sooner.

It was indeed a performance bug when setting elements in a map/set that caused the underlying bucket structure to be constantly reallocated. Fixed now and should be much quicker.

Regarding your last comment on update: Could you please open a separate issue for this providing some more details if it is still an issue for you? Thanks!

[uriva]

can you release so I can check this and update again? thanks!

[tobgu]

Released in v0.19.2.

[uriva]

doesn't look like it's fixed, the last command still takes many seconds for adding a single element.

[tobgu]

I think that depends on if 1 is already in the set or not. If not, then it will still take a long time since the underlying bucket structure is still reallocated when you add new elements to a map that has a too high load factor (where there are too few buckets for the number of elements in the map/set).

I don't think there's anything I can do about it with the current underlying structure of the pmap.

I wonder, however, what the real world use case is for the example provided in this issue? I could understand something like:

x = [random.randint(0, 1000000) for _ in range(1000000)]
ps = pyrsistent.s(*x)
for i in range(10): ps = ps.add(1)

Where you overwrite ps with a reference to the new set (and this should be amortized O(1)). In the original example you repeatedly add the same object to the same set (creating a new set that's not used) over and over again.

[uriva]

even if add happens only once, it may take multiple seconds on a considerable amount of random cases.

as for anything to do about it or not, i leave to your judgemenet, but in immutables it seems to work immediately.