Linear search when releasing a sample scales very poorly

[gpalmer-latai]

Linear search when releasing a sample scales very poorly

[gpalmer-latai]

Took another look. There doesn't seem to be any issue with removing a chunk when we know its index in the UsedChunkList. That would essentially just skip to this line of code:

iceoryx/iceoryx_posh/include/iceoryx_posh/internal/popo/used_chunk_list.inl

Line 78 in b2e4137

chunk = m_listData[current].releaseToSharedChunk();

[gpalmer-latai]

Yes so, after my first quick pass I'm thinking we can update the API's in the following way to achieve the goal of eliminating this linear search:

1. For UsedChunkList::insert, instead of returning a bool, return an expected<uint32_t, InsertChunkError>, where the uint32_t is the index into m_listData where the chunk was inserted
2. In ChunkReceiver::tryGet(), instead of returning expected<const mepoo::ChunkHeader*, ChunkReceiveResult>, it should return expected<UsedChunk, ChunkReceiveResult> where UsedChunk is a struct containing a const mepoo::ChunkHeader* and the uint32_t index where that chunk lives in the used chunk list.
3. This should get propagated out to SubscriberPortUser::tryGetChunk()
4. And again to BaseSubscriber::takeChunk()
5. In Subcriber::take(), the deleter around the sample unique pointer should call releaseChunk() with the modified UsedChunk object
6. SubscriberPortUser::releaseChunk should get updated to take the UsedChunk datastructure instead of the chunk header
7. ChunkReceiver::release gets updated to take UsedChunk instead of the chunk header
8. UsedChunkList::remove gets updated to take the UsedChunk instead of the chunk header
9. It then skips the linear search and directly looks up the data in m_listData given the index stored in the UsedChunk struct. To check out logic is sound we add a contract check validating that m_listData[usedChunk.index].getChunkHeader() == usedChunk.header

[elfenpiff]

@gpalmer-latai This approach could work for the good case. But keep in mind, the UsedChunkList is a lock-free construct, and they often have unpleasant surprises for you that may need weeks to fix.

But the bad case still has some problems. When an application crashes and someone has to iterate once over 100.000 chunks to clean them up manually you will see a hick up in the system where suddenly, due to a crash, the runtime increases. This is maybe unacceptable for a real-time system and for a safety-critical one (freedom from interference).

The point I am trying to make is, that we can for sure apply your solution but in my opinion it maybe solves a problem that should not exist in this current form. I do not doubt the use case but the used messaging pattern (publish-subscribe). Could you tell us a bit more about the setup, especially:

1. How many subscribers do you have? (I assume just 1 or 2)
2. How many publishers do you have? (I assume many)
3. And the overall task? (I assume some kind of logging)

In iceoryx2 we have planned messaging patterns also like: pipeline & blackboard and those could be easily manually implemented in iceoryx since all the right building blocks are already here.

[gpalmer-latai]

But keep in mind, the UsedChunkList is a lock-free construct

This isn't relevant as the data structure is not meant to be used concurrently. It is even explicitly NOT thread safe. It exists in shared memory only to allow RouDi to clean up when the subscriber process crashes.

But the bad case still has some problems. When an application crashes and someone has to iterate once over 100.000 chunks to clean them up manually you will see a hick up in the system where suddenly, due to a crash, the runtime increases

Not so. While RouDi will not have the index, it doesn't really matter. RouDi doesn't need to release the samples in any particular order so it can simple iterate forward through the list, releasing everything with O(n) time complexity. For 100,000 samples this is probably just a ~10ms operation.

The problem described in this issue has to do with random access time complexity. But the solution is the same as it is for a std::list - simple allow a version of remove which takes an index/iterator to the element's position, known when it is inserted.

[gpalmer-latai]

As for our setup.

1. There are just a few subscribers per topic, usually, yes. But there could be more depending on the use case.
2. The problem described here applies to just a single publisher/subscriber (as I've shown in my example). In general though we might only have one publisher on a topic, or we might have many.
3. The important information about the task is that we maintain a buffer of recent history, whose size correlates to the overall publish rate of the topic.

As a mitigation we are already exploring batching to reduce publisher sample count, but that can only help to an extent and is not always possible.

It is also worth noting that we can't rely on our pattern of access here to solve the problem. For example - when we drain samples with oldest samples first, we are hitting the worst case scenario because the oldest samples are at the back of the used chunk list. You might solve this problem by somehow allowing reverse iteration of the list, but we will still have other release patterns with relatively new and in-the-middle samples.

[elfenpiff]

@gpalmer-latai

This isn't relevant as the data structure is not meant to be used concurrently. It is even explicitly NOT thread safe. It exists in shared memory only to allow RouDi to clean up when the subscriber process crashes.

I think it is used concurrently. Whenever a publisher delivers a sample, it calls UsedChunkList::insert() in ChunkSender::tryAllocate() and the subscriber calls UsedChunkList::remove() when releasing the chunk in ChunkReceiver::release(). This is somehow hidden, but getMembers() in both constructs should return the data to the same underlying construct.

But it is possible that I get this wrong, since I am not so familiar with the source code anymore. @elBoberido I think you are the one who implemented it, maybe you can shine some light on it.

Addendum: I was wrong, the list must just be synced with RouDi.

[gpalmer-latai]

No worries 🙂

I just took a closer look and there is a slight complication to the approach I outlined. In true forward list fashion, list removal does unfortunately require knowing the index to the previous element:

iceoryx/iceoryx_posh/include/iceoryx_posh/internal/popo/used_chunk_list.inl

Line 87 in b2e4137

m_listIndices[previous] = m_listIndices[current];

Will have to do some more brainstorming to figure out what additional info needs to be stored where to make this work.

The first obvious solution that pops out to me though is that we simply return from insert and take as an argument to removal:

struct UsedChunk
{
  const mepoo::ChunkHeader* chunkHeader;
  uint32_t current;
  uint32_t previous;
}

[gpalmer-latai]

Note that this information basically gets immediately plumbed into the deleter of a unique_ptr here

[gpalmer-latai]

Ah, but the untyped subscriber doesn't so neatly encode a destructor: https://github.com/gpalmer-latai/iceoryx/blob/e97d209e13c36d71237c99e0246310b8029f8f26/iceoryx_posh/include/iceoryx_posh/internal/popo/untyped_subscriber_impl.inl#L54, so we'd have to store this information elsewhere...

[elfenpiff]

@gpalmer-latai Instead of using some kind of list, couldn't you fill the m_listData with optionals and set them to nullopt when it is no longer set?

[gpalmer-latai]

@gpalmer-latai Instead of using some kind of list, couldn't you fill the m_listData with optionals and set them to nullopt when it is no longer set?

The performance hit isn't in removal of the elements. It is in locating where they are. Setting aside the quirks of implementation (every operation has to be on less than 64 bits because of torn writes), the UsedChunkList is more or less just a typical forward list. Removal is O(1) provided you already know the location of the data in the list. That is the part that is missing here.

[gpalmer-latai]

So following along my line of thought here - using

struct UsedChunk
{
  const mepoo::ChunkHeader* chunkHeader;
  uint32_t current;
  uint32_t previous;
}

in the UsedChunkList API's would be sufficient to facilitate O(1) removal. It is similar to how a std::list::insert will yield you an iterator.

The problem then becomes plumbing this through the rest of the stack. For the typed API's it is relatively simple. You just bubble this data structure up to where the sample is created and plumb it into the deleter of the iox::unique_ptr: https://github.com/gpalmer-latai/iceoryx/blob/e97d209e13c36d71237c99e0246310b8029f8f26/iceoryx_posh/include/iceoryx_posh/internal/popo/subscriber_impl.inl#L49

The catch is untyped APIs. They currently only return void * pointers and have separate release(void*)/publish(void*), etc... methods. I can think of a few options to handle these:

1. Instead of returning void*, return something like the UsedChunk but with the pointer being to the payload and the indices possibly being private with friend access to the publisher/subscriber classes. This is quite ugly and users would have to adapt code to handle these ugly things. It might be less ugly if you add some operator->, but still...
2. Instead of returning void*, return directly or wrapped a iox::unique_ptr<void*> with the same custom deleter logic as the typed API's. Remove the release methods and change the untyped API's to use the same RAII logic as the typed ones. Users then have to call sample.get() to get the void* pointer, which they can then use the same way as before. We could even add some convenience methods to make this easier such as

template <typename T>
T* UntypedSample::getTyped()
{
  return static_cast<T*>(m_ptr.get());
}

[gpalmer-latai]

If it is preferable to you I'm happy to speak about this problem synchronously via some video chat. It is a bit of a high priority issue for us and I intend to implement some solution immediately.

[gpalmer-latai]

There is also a compromise solution. We could add the plumbing to allow typed endpoints to have fast removal by referencing the insertion index in those custom deleters, but leave the untyped endpoints alone and fallback to linear search.

I'm not a fan of this solution because of the general complexity of supporting two different paths, and also because it will require us to replace our usage of the untyped subscriber with typed ones, which won't be trivial because we actually rely on the type-erased nature of samples received this way, extracting the size from the header. Using typed API's instead would require some ugly hackery. I think it is doable, but still...

[gpalmer-latai]

Ah shoot, realization just dawned on me about a flaw in my proposed solution here.

We cannot simply store the previous element index in the returned data structure, because the previous element could be removed, invalidating this index. Instead what we probably need to do is make this a "doubly linked list" by adding a m_listIndicesBackwards.

[gpalmer-latai]

Hah, cool. iox::unique_ptr supports type erasure unlike std::unique_ptr because of the non-templated deleter. Neat. Seems like we really could return a Sample<void, H> for untyped endpoints.