Serious bug in array!

niko · Post by **niko** » Thu Apr 21, 2005 12:53 pm

I like vox's solution, and I think it would be ideal. Passing the parameter by value is no option for me, but copying it in case of a reallocation is just fine. I think this should not impact performance.

jox · Post by **jox** » Thu Apr 21, 2005 1:02 pm

Electron wrote:...if you're going to make a temporary copy of new the element before reallocation then it should be faster to just pass by value...

I dont think it will make a big difference. Passing by value also creates a temp element and copies the contents. So there's not such a big difference.

Electron wrote:...,except of course in situation where reallocation isn't needed. So I'm not sure what the most efficient solution would be.

Thats the point. In most cases reallocation is NOT needed. Or in other words, reallocation is only needed now and then. The bigger the array grows, the bigger also the (reserved) space for additional elements grows. This can btw. result in large unused memory blocks, but that's another story.

Also, reallocating in itself is quite non-efficient. So, creating a temp element for saveness shouldn't be a deal.

If you need high effiency, then you should considder using c++ arrays and not core::array. core::array is there for your convenience with possible cost of some efficency.

hybrid · Post by **hybrid** » Thu Apr 21, 2005 1:09 pm

Vox had another solution which would always leave at least one free slot, i.e. check if after adding the element to the array the array is full. In that case reallocate, but his time it would be after insertion so no problem with inserting the element. This would slightly increase the memory allocation, but you won't notice on the average. It just changes the case where the number of stored elements is always the same as the allocated space. Only in that case the memory allocation is done, but would not be needed. Otherwise you have the same behavior. It's a trade-off between mem usage and speed.

Electron · Post by **Electron** » Thu Apr 21, 2005 1:09 pm

yeah.That makes sense. Sorry for being difficult

jox · Post by **jox** » Thu Apr 21, 2005 1:21 pm

hybrid wrote:Vox had another solution which would always leave at least one free slot, i.e. check if after adding the element to the array the array is full. In that case reallocate, but his time it would be after insertion so no problem with inserting the element. This would slightly increase the memory allocation, but you won't notice on the average. It just changes the case where the number of stored elements is always the same as the allocated space. Only in that case the memory allocation is done, but would not be needed. Otherwise you have the same behavior. It's a trade-off between mem usage and speed.

Yes thats another solution. But it has a disadvantage if you want to allocate the array yourself before filling it up. Imagine you have 1000 elements and call reallocate(1000) before calling push_back a thousand times. If reallocation occurs after pushing to maintain at least on free slot, you got an array of 2000 slots and 1000 used elements afterwards. The workaround would be to call reallocate(1000+1) in the beginning, but that kinda ugly in my opinion...

hybrid · Post by **hybrid** » Thu Apr 21, 2005 1:40 pm

jox wrote:The workaround would be to call reallocate(1000+1) in the beginning, but that kinda ugly in my opinion...

Ok, so there are always special cases to handle. There is either the test in push_back with an optional object copy or the special case of having an additional element allocated (if you change the initial allocation to 1001 in case of array(1000)). But due to the doubling of allocated space each time the waste of memory could become non-neglectible whereas a copy action on each reallocation could indeed be less painful. Except if such reallocations would occur to often - which would mean someone created a much too small array?! Ok, so copying seems to be the best solution.