News for hackers. Stuff that matters.
Re: by tialaramex on Tuesday April 30, 2024 @08:12AM (#40210151)
It makes sense to potentially be ignorant of capacity because it's just an optimisation. Your growable array type (the thing most likely to have capacity because it will definitely have the amortized growth strategy, even Python doesn't get that wrong) doesn't need to even reveal this feature to you†, whereas length is an actual property of the container.

† It should because even a very high level programmer can significantly impact performance by providing useful hints here, but it doesn't have to. And hey C++ programmers think they're writing low level code and their hint API is rubbish (and the language's inventor says you shouldn't bother providing hints as a result) so apparently you're in good company.

It's actually interesting where capacity is used, and of those places where it's available to the programmer to influence. In principle a lot of types could benefit from smarter growth strategies, but often only the growable array type (and maybe a string type if your language at least knows those aren't just growable arrays) is given a suitable API.

For example even crappy 1980s-style hash tables could avoid allocation overhead with a pre-allocation scheme based on size hints, ie knowing capacity. All the Open addressed hash tables can do even better here because it's a natural fit for them.

There are no comments on this comment yet.