2 ms·

The overhead of ArrayList reallocations is no more disruptive at small scales than it is at large scales. (Of course, the total memory needed at large scales ca

The overhead of ArrayList reallocations is no more disruptive at small scales than it is at large scales. (Of course, the total memory needed at large scales can be disruptive, but that's fundamental. If you've got a lot of elements, you need a lot of memory for them.) ArrayLists grow by allocating a new buffer whose size is a multiple of the current size. This means that as the buffer size gets bigger, the reallocations become less frequent. The end result is that appending to an ArrayList has constant time amortized complexity, even though it will periodically do increasingly large copies. https://en.wikipedia.org/wiki/Amortized_analysis https://en.wikipedia.org/wiki/Amortized_analysis I bombed an interview once because my interviewers didn't understand amortized analysis and I wasn't able to get them to understand it.

oldsecondhand 4y ago
> (Of course, the total memory needed at large scales can be disruptive, but that's fundamental. If you've got a lot of elements, you need a lot of memory for them.) But in case of a linked list that large amount of memory doesn't have to be contigous, and you don't have to perform a lot of copying all at once which kills responsiveness.
- munificent 4y ago
  > But in case of a linked list that large amount of memory doesn't have to be contigous True! Though in rare cases where that becomes a problem, you are probably better off doing a hybrid solution where you store the data in a relatively small number of chunks or pages. If you have so much data that you are having trouble getting a contiguous allocation, you probably also can't afford the overhead of an additional pointer for each element, which is what a linked list would give you. > you don't have to perform a lot of copying all at once which kills responsiveness. I believe there are ArrayList implementations that distribute the copy across a series of operations to mitigate this, but, yes, latency can be an issue for some use cases. (In general, though, my experience is that people overestimate how long it takes to copy a contiguous block of memory.)

oldsecondhand 4y ago

> (Of course, the total memory needed at large scales can be disruptive, but that's fundamental. If you've got a lot of elements, you need a lot of memory for them.) But in case of a linked list that large amount of memory doesn't have to be contigous, and you don't have to perform a lot of copying all at once which kills responsiveness.

munificent 4y ago
> But in case of a linked list that large amount of memory doesn't have to be contigous True! Though in rare cases where that becomes a problem, you are probably better off doing a hybrid solution where you store the data in a relatively small number of chunks or pages. If you have so much data that you are having trouble getting a contiguous allocation, you probably also can't afford the overhead of an additional pointer for each element, which is what a linked list would give you. > you don't have to perform a lot of copying all at once which kills responsiveness. I believe there are ArrayList implementations that distribute the copy across a series of operations to mitigate this, but, yes, latency can be an issue for some use cases. (In general, though, my experience is that people overestimate how long it takes to copy a contiguous block of memory.)