Tim Peters wrote:
> The overallocation strategy gets more complicated, though, and less
> effective for prepending. If you run out of room when prepending, it's not
> enough just to ask realloc() for more memory, you also have to memmove() the
> entire vector, to "make room at the left end". In previous lives I've found
> that "appending at the right" is as efficient as it is in practice largely
> because most non-trivial C realloc() calls end up extending the vector
> in-place, not needing to copy anything. The O() behavior is the same if
> each boost in size has to move everything that already existed, but the
> constant factor goes up more than just measurably <wink>.
Shouldn't you malloc() in the case of prepending, and do the copying
yourself? realloc can only avoid copying if it can append a free block.
For the list, we know
a) realloc is unlikely to find a new block, anyway, as it is pymalloc,
which never extends a small block.
b) even if realloc would be able to extend the block, we still would
have to copy the data.
I don't know whether the overallocation would make similar-sized room
at both ends, or whether it would take the current operation into
account. For the specific case of queues, we may find that doing
*just* the copying might be sufficient, with no need to go to the
allocator.
Regards,
Martin
RetroSearch is an open source project built by @garambo | Open a GitHub Issue
Search and Browse the WWW like it's 1997 | Search results from DuckDuckGo
HTML:
3.2
| Encoding:
UTF-8
| Version:
0.7.4