(New idea) Resizing an array: Dangerous? Possibly buggy?

[Jonathan M Davis]

On Friday 11 March 2011 21:40:36 %u wrote:
> >> I think pitfalls like this one (with the garbage collector, for example)
> >> should definitely be documented somewhere. I would imagine that quite a
> >> few people who try to set the length of an array
> 
> won't realize that they can run out of memory this way, especially because
> it's nondeterministic in many cases.
> 
> > If you're referring to reducing the length of an array, I think people
> > with a C background would expect the memory not to be reallocated,
> > because this avoids copying memory contents, and anyway
> 
> the array may grow again.
> 
> > I think this is documented somewhere, maybe TDPL when talking about
> > slices. But making people more aware of it is probably a good thing.
> > Perhaps an article on things to watch out for to prevent
> 
> the GC holding onto too much memory would be useful.
> 
> 
> I'm having an idea: Why not automatically reallocate/shrink an array when
> it's resized to below 25% of its capacity, and automatically double the
> capacity when it overflows? That way, we're never on a boundary case (as
> would happen if we simply shrunk the array when it was below 50% capacity
> rather than 25%), we could free memory, and the operations would be really
> O(1) (since the copies are amortized over the items)... does that sound
> like a good idea?

No. That means that you have to worry about reallocation at fairly 
unpredicatable points. If you really want that behavior, it's easy enough to 
create a wrapper which does that. However, you can't get the current behavior by 
wrapping an array that behaves as you suggest. Also, what you suggest adds 
additional overhead to every operation which could potentially resize an array. 
On the whole, the way arrays work right now works quite well.

- Jonathan M Davis