search

griba2001 / urweb-aatree

Sorted and Hashed versions of Sets and Dictionaries as Arne Anderson trees in urweb.
2 stars 0 forks source link

Memory consumption #1

Open sergei-mironov opened 9 years ago

sergei-mironov commented 9 years ago

Hi. I've faced a memory consumption problem while working with UrWeb lists, please see http://www.impredicative.com/pipermail/ur/2015-March/001917.html Looks like UrWeb has very simple memory allocation strategy. I don't understand the whole picture, but I suppose that aatree may suffer from the same issue.

It is interesting for me, how does Map.insert behave. Does it copies whole tree structure or it is able to re-use the memory (may it allocate memory for new items only)? How does rebalancing affect memory in this case?

Regards, Sergey

griba2001 commented 9 years ago

I followed the algorithm explained at the wikipedia, turning it functional https://en.wikipedia.org/wiki/AA_tree

Insert rebalancing (functions skew and split) may create new nodes. This is a functional implementation for a functional language, not an imperative one.

The system should made possible to enlarge the heap appropiately.

griba2001 commented 9 years ago

I meant the "Ur/Web" run time system should provide heap allocation as needed.

I don't see any memory wasting procedure on Insert. Delete rebalancings use more nodes, but this comes with the AA_tree model.