sebastian-philipp / StringMap

Haskell Project to convert the PrefixTree of the Holumbus into it's own Hackage Packet
MIT License
1 stars 5 forks source link

Feature: Improve Update and Delete performance by introducing parallelism #6

Open chrisreu opened 10 years ago

chrisreu commented 10 years ago

We discussed this idea before, but never really implemented it. Deletes and Updates generally have to traverse the whole StringMap. If i'm not mistaken, deletes are even implemented using update. This makes both operations potentially expensive.

There is a way to potentially speed up the updates, at least for big StringMap's. If we split up the StringMap at it's top level, we can traverse the resulting branches in parallel. After the parallel updates the branches can be merged again. Splitting and merging should be considered cheap here.

sebastian-philipp commented 10 years ago

My last comment was wrong. Another Idea would be to build a Stringmap of to-be-deleted keys and then call difference with the original StringMap