-1

I'm looking for a data structure that supports O(1) random access and worst case O(1) append. In my case however, O(1) amortized time for append is not what I'm looking for.

The data structure also will not have any operations performed on it other than append and access. No deletions, no insertions, just an append-only structure.

In my case, the upper bound would be very large, maybe 8GB.

Also, this question is basically identical to this, however, the problem I have with the answer on that question is that it discounts the cost of memory allocation. Memory allocation is most of the time O(1) in c++, however, there are many times I've experienced where malloc takes a long time.

I was wondering if a structure like this can even exist. I read this pdf, however I believe the worst case time complexity on that is still O(1) amortized.

If anybody has any ideas for a structure that can support these conditions (not looking for implementation, just an idea), that would be greatly appreciated.

CinCoutSinBla
  • 3
  • 3
  • An equally valid question is can such a structure exist? – user4581301 Apr 20 '21 at 01:26
  • Yes, that would be an equally valid question – CinCoutSinBla Apr 20 '21 at 01:27
  • What constraints on size do you have? Is there an upper bound? Is there a reasonably anticipated number of elements? All would be considerations for how to approach this. – David C. Rankin Apr 20 '21 at 01:28
  • In my case I dont think it would have an upper bound, but maybe up to a point (like 8GB) – CinCoutSinBla Apr 20 '21 at 01:29
  • Ouch `:)` My reason for asking was this. If you know you will on average have a billion elements (in your case), you can mitigate the cost of allocation by allocating for the anticipated number of elements up front. At that point you would have O(1) access/appent until a reallocation is needed. Then knowing by how much you may overrun the initial allocation would allow a single reallocation to cover most cases. With `malloc` now defaulting to `mmap` in most cases, the cost of reallocation is also mitigated compared to what it has been in the past. – David C. Rankin Apr 20 '21 at 01:36
  • With a defined upper bound, and if you discount the initialization time for the structure itself, it's easy (allocate to the max up front). Otherwise, the problem is impossible as stated. – hobbs Apr 20 '21 at 01:37
  • @DavidC.Rankin You're right, but in my case the data starts out with length zero, and it will very rarely ever get above 2GB, and especially 8GB. It mostly will have an avg length of a few MB. – CinCoutSinBla Apr 20 '21 at 01:38
  • A good trade-off between allocation cost and growth is to simply allocate, say, an initial 4M block and then each time a reallocation is needed, double the current size. This gives you growth of `4, 8, 16,32,64, 128, 256, 512 1024, ...` So you see you could grow from 4M to 1G only 8 reallocations. That covers a very wide range of sizes. You would grow to 8G in only 11 reallocations. You can add limits as well. Say once you reach 8G, you simply grow by 1G thereafter. – David C. Rankin Apr 20 '21 at 01:41
  • @DavidC.Rankin I thought of that at the start too, however if you keep doubling the size, then the cost of a `malloc` will increase too. Assuming the worst case for `malloc` is O(N), then this wouldn't work. – CinCoutSinBla Apr 20 '21 at 01:43
  • @DavidC.Rankin I'm mostly trying to avoid any large lag spike. – CinCoutSinBla Apr 20 '21 at 01:43
  • Not really. Here is where `malloc` using `mmap` comes into play. If there is memory available, then in most cases `realloc` can simply add to the current allocation without forcing a copy/free. These are all ***profiling*** consideration. Get the code working first and then profile if you have performance issues and find out where the challenge is. If this is a server situation where you must continually serve access/append requests, you could even create a cache of the most frequently accessed items and buffer new appends during reallocation or some such scheme. – David C. Rankin Apr 20 '21 at 01:45
  • @DavidC.Rankin You're right about that. I did actually make a simple implementation of this, but I found large lag spikes some of the time. – CinCoutSinBla Apr 20 '21 at 01:48
  • Bottom line, you are not going to beat a dynamic plain-old-array for simplicity -- that just leaves what reallocation scheme to use. Get it working with the good information from your article and here and see how it goes. Then tweak the reallocation scheme or consider a cache/copy and buffer for access/appends during reallocation to make it completely transparent to your users (if anything is needed at all) KISS (Keep it Stupid Simple -- unless that just won't work) – David C. Rankin Apr 20 '21 at 01:52
  • Why not just allocate the max amount of memory (8GB) and just use an array. – DollarAkshay Apr 20 '21 at 01:59
  • @DollarAkshay Well because I obviously don't want the application to use 8GB of memory for just 4MB of actual data (99% of the time) – CinCoutSinBla Apr 20 '21 at 02:01
  • You could take the `std::deque` approach: allocate an array of _pointers_ to `T` up front and then when new elements are appended allocate a fixed-sized array of `T` if more space is needed and add it to the array of pointers. Size the initial array of pointers and the size of each "node" such that you never need to re-allocate anything and you maintain O(1) appends. You still have some appends that are more expensive, since they have to allocate memory, but their expense doesn't depend on the number of elements in the container; each one costs the same. Or just use `std::deque`. – Miles Budnek Apr 20 '21 at 02:07
  • @MilesBudnek Do you mean basically have an array of pointers, where each pointer points to a buffer with a fixed size? I implemented this except with an std::vector of pointers, not deque – CinCoutSinBla Apr 20 '21 at 02:12
  • Exactly. That's what `std::deque` does internally. – Miles Budnek Apr 20 '21 at 02:15
  • @MilesBudnek Oh ok. Should I switch to an std::deque then? – CinCoutSinBla Apr 20 '21 at 02:15
  • If your elements are `char*`s, then sure; I would recommend `std::deque` for that purpose though, since `std::string` will manage the lifetime of its buffer for you. Or if this is just a big collection of `char`s and not strings, then `std::deque` would work. – Miles Budnek Apr 20 '21 at 02:19

1 Answers1

2

std::deque gets awfully close to what you want:

  1. It's O(1) for random access (twice as expensive as std::vector, as it must perform two pointer dereferences, not just one, but a fixed multiple like that doesn't change big-O)
  2. It's effectively O(1), not just amortized O(1), for append, if you consider intermittent fixed size memory allocation (without initialization) to be O(1) (which it is; it's not constant cost, but the costs are not tied to the size of the deque)

Unlike the allocation in your linked question (when the newly allocated memory doubles in size, and therefore new allocations grow linearly), std::deques block allocations are fixed size, so you're either:

  1. Inserting an element into existing allocated space, or
  2. Allocating a block of fixed size, then inserting an element into the first slot of the new block

Since the new blocks are of fixed size, not continuously growing, it's still O(1) (sometimes O(1 construction) sometimes O(1 fixed size allocation + 1 construction), but still unrelated to length of the deque).

ShadowRanger
  • 143,180
  • 12
  • 188
  • 271
  • How would you specify the fixed buffer size of the deque though? For example, if I had a `std::deque`, what would its buffer size be? – CinCoutSinBla Apr 20 '21 at 02:17
  • However, this link: https://stackoverflow.com/a/22307025/15699083 shows that std::deque has O(1) amortized time complexity for appending. I think it's true cause an std::deque I believe uses an std::vector internally, and growing is O(1) amortized – CinCoutSinBla Apr 20 '21 at 02:19
  • @CinCoutSinBla: The standard doesn't allow you to specify block sizes (GCC's implementation used to allow this, but removed it when they realized it violated the standard). It varies by implementation, e.g. 64 bit `libc++`'s approach, according to cppreference, is blocks large enough for 16 elements, or 4096 bytes, whichever is larger. – ShadowRanger Apr 20 '21 at 02:20
  • Ah ok. Did you see my comment with the link about the amortized time though? – CinCoutSinBla Apr 20 '21 at 02:21
  • 1
    That answer is incorrect. The standard specifies constant time for insertion at the beginning or end of a `std::deque` see [deque.modifiers](https://timsong-cpp.github.io/cppwp/deque.modifiers). – Miles Budnek Apr 20 '21 at 02:24
  • @CinCoutSinBla: The answer you quote misquoted its source; both the standard and cppreference specify constant `O(1)` time for append. I'm curious about that myself (I don't see an obvious way to avoid an admittedly low data volume, incredibly infrequent resize of the bookkeeping data that would be only amortized, not constant, `O(1)`, so infrequent and so low cost as to be ignorable, but still *technically* having some operations that do `O(n)` work with a huge constant divisor), but that's what the standard says. – ShadowRanger Apr 20 '21 at 02:25
  • Ah ok. I’m going to accept this, as it seems good. Thank you guys! – CinCoutSinBla Apr 20 '21 at 02:28
  • Looking through the libstdc++ code for `std::deque` there is indeed some hidden amortized constant behavior for re-allocating the "map" array as they call it. It starts with slots for 8 512-byte nodes (so 4kb of data) and doubles in size on each reallocation. I haven't looked at other implementations, but I suspect they do the same. Using a huge initial array or huge nodes would be pretty wasteful for small containers. – Miles Budnek Apr 20 '21 at 02:44