undefined | Better HN

0 pointsjstimpfle12d ago0 comments

I don't know the size up front because it goes up and down depending on load. I want to be able to buffer jitters/spikes but not hog memory when there is no data in the queue. I was assuming it's natural to want a simple linked list of chunks to represent this, maybe chunks can be partially full here. So chunk -> chunk -> chunk, and each chunk is actually a node with a buffer pointer + size + fill fields, or maybe the data comes directly after the size + fill fields so no buffer pointer needed.

That easily gives O(1) access to enqueue/dequeue, and the queue naturally grows and shrinks (even within configurable bounds) as part of reading and writing. Blocks can be taken and returned from/to some fixed size block pool. This design would be completely satisfactory. It's also very easy to code from scratch, so why should I settle for anything less, for example a growable vector where a reallocation would mean blocking other threads for extended time? But I was told to "not reinvent the wheel" and to "not overengineer it" so I tried to change my mind and make use of an STL container data structure.

> our disagreement seems to be that you think a slightly different terrible data structure would be a good idea

I don't know why you think that I would be thinking that, and I'm confused that you say you were gesturing at how std::deque is terrible, and not sure why I should be the one misconstruing something, when my premise from the beginning was "STL containers are terrible in many ways". And I don't get at all why you responded with "basically std::deque" to my "maybe chunk lists would better". It doesn't make the least bit of sense to me.

But let's settle this here, this is a pointless fight...

0 comments

2 comments · 1 top-level

tialaramex11d ago· 1 in thread

> I was assuming it's natural to want a simple linked list of chunks

In the 1970s or 1980s that does feel entirely natural, but in the 1990s the 68040 and i486 both introduce L1 data cache and so now all list chasing hurts very badly, your structure is a list chase any time we index into the collection.

I think I can see a way to have what you're describing hit amortized O(1) push/ pop with the spikes which are amortized being more frequent (linear with capacity) but fixed size and smaller (allocate or free one block then do some housekeeping), it costs more RAM because of the block overhead and it is no longer contiguous, but I see that for your intended application you probably don't care about either problem.

Now that I think I understand your data structure better it's much less similar to std::deque than I had originally thought, it does seem very niche to me, but more power to you if you write such a type.

jstimpfleOP11d ago

Yes, I am talking about a buffer for an outbound queue that should buffer on the order of MB/sec. That's decidedly not a niche thing. It's very basic systems engineering (and also how socket buffers are represented in a kernel for example).

You would chunk this at a reasonable size, at least multiple kilobytes per chunk. That is not slow, it is basically the only way to do it. Yes, that is amortized, bounded overhead. Sure it costs a bit of extra RAM, like one extra pointer and maybe 1-2 integers per chunk? For chunks of 4 KB, this overhead is predictably less than 1 % plus less than 1 chunk worth of fragmentation in the last chunk. That is NOT unpredictable spikes of > 100 percent during reallocation or 100000 percent due to low utilisation...

I believe you can even instruct the CPU to preload the next buffer while still streaming the last, but personally have never had the need to dive _that_ deep. It would probably be very hard to measure any performance benefit from doing so. I like to write very basic straightforward C code, just solve the data structure problem first, not hand-wave it.