Re:Show HN: Array with Constant Time Access and Fast Inserti...
by quickthrower2 on Wednesday September 04, 2019 @03:45PM
(#20880716)
I think it would do some stuff slower. It's probably a boring old trade off. Like you'd make if you swapped arrays for linked lists.
Where I think this would be slower is streaming access. Say you have 10,000 elements, this would store it in a 100 by 100 grid. You want to read off elements 200-500.
A normal array would allow you to sequence through them as a continuous block of memory, probably as fast as it gets. I'm outside my expertise here but I believe that block could be loaded into the processors inner most cache?
This array OTOH would require some indexing/pointers along the way which would slow it down.
So this will add to some of the constants that the O notation conveniently omits!
Where I think this would be slower is streaming access. Say you have 10,000 elements, this would store it in a 100 by 100 grid. You want to read off elements 200-500.
A normal array would allow you to sequence through them as a continuous block of memory, probably as fast as it gets. I'm outside my expertise here but I believe that block could be loaded into the processors inner most cache?
This array OTOH would require some indexing/pointers along the way which would slow it down.
So this will add to some of the constants that the O notation conveniently omits!