1

I have a list of items and I would like to retreive items from this list according to an algorithm. I will use strategy pattern to inject algorithms like FIFO, MFU, LRU, etc. For example, in FIFO I planned to use a concurrent queue to peek the first element and then move it to the end. The problem is that Enqueue and Dequeue are tread safe, but not atomic. This means that two threads may access in parallel when I call to the two methods (the first thread may finish dequeue and the second will dequeue before enqueue on first thread finished).

I was asking myself what is the better approach to solve this:

  1. Add lock around the two methods? (Dequeue and Enqueue)
  2. Lock two methods but using a regular Queue to avoid double lock (my lock and the concurrent queue lock)
  3. Use any other thread safe collection?

Thanks

Alex
  • 47
  • 4
  • *"Add lock on the two methods?"* -- Which two methods? And how do you intend to add the `lock`? Could you include in the question an example? – Theodor Zoulias Apr 05 '23 at 09:45
  • @TheodorZoulias The two methods is the call to Dequeue and Enqueue as described in the question. There is no code, just planning how to implementation it. – Alex Apr 05 '23 at 10:23
  • It seems that you have some concrete ideas about how to implement your algorithm, and you could present your ideas as concrete code. Otherwise we have to imagine what you mean with *"Add lock around the two methods"*, and what we imagine might differ from what you have in mind. You can increase the likelihood of getting useful answers by improving your question and making it more unambiguous. – Theodor Zoulias Apr 05 '23 at 10:55

1 Answers1

1

I would start with option 2. Use a regular queue and lock it.

If you already have a lock there should be little reason to use a thread safe collection. Just note that while the locking overhead is low for uncontested locks, if your list is accessed very frequently from multiple threads you might want some other strategy. But designing high performance thread safe collections is difficult, and not something I would attempt without a great deal of study.

As always, profile your algorithm & program to find out the bottlenecks and usage patterns.

JonasH
  • 28,608
  • 2
  • 10
  • 23
  • I have a service that may receive thousands of objects every minute (one or multiple messages). Then, I create the object using Parallel.ForEach so many threads nay access that collection to pick a random color. Do you think that my approach is good? @JonasH – Alex Apr 05 '23 at 08:43
  • @Alex thousands of objects every minute is on the order of a message per 10ms, that is not a lot. Using a parallel loop just to accesses a locked collection is rarely a good idea, you are just trashing the cpu caches for no good reason. Start with a single threaded solution, profile it to find problem areas, improve the algorithm etc. until you have sufficiently good performance. – JonasH Apr 05 '23 at 08:48
  • What is considered a lot? just to consider it in the future. A better idea can be using a regular list and lock a data member that saves the current index. When the index is at the last of the list, I reset to 0. It will save moving an element in the queue every time. What do you think? it is strange that I didn't see this approach on other answers – Alex Apr 05 '23 at 08:52
  • @Alex I would refer to [Latencies every programmer should know](https://gist.github.com/jboner/2841832) to get a scale of time. – JonasH Apr 05 '23 at 08:53
  • Actually I have a type of object that can be sent up to two messages per second and up to 10 thousand of objects for every message. Other types are coming rarely but for every element I need to update a lot of properies in WPF application and after test it I see better performance. – Alex Apr 05 '23 at 08:56
  • @Alex What you are describing is a "Circular buffer" or "ring buffer", Using a lock for the index may be appropriate, but there is no real way to tell without knowing the specific application and performance requirements. Again, *profile your application*. – JonasH Apr 05 '23 at 08:58
  • I will not use a circular buffer because the list is initiated only once. I need lock only for read and not read/write. After reading this link: https://stackoverflow.com/questions/25436064/does-locking-with-many-different-objects-has-an-impact-performance-wise-comparin – Alex Apr 05 '23 at 09:13
  • I understand that lock is cheap when thread already owns it. I pick a color only for first time, which means that only first time for every object in first message, I pick a color. I will lock the index because I need to ensure that same color is not selected twice. Next messages will be handled faster because color is already selected. In addition, the parallelism is handled by C# and will not use many threads if not necessary, I also configured max number of parallelism. – Alex Apr 05 '23 at 09:16
  • @Graffito `index++` *is not* atomic, `Interlocked.Increment` *is*. Ofc, if the goal is to assign m colors to n items you could just do: `colorList[itemIndex % colorList.Count]`, no need for to update any index at all. Parallel.For/Foreach can give the itemIntex. – JonasH Apr 05 '23 at 11:59
  • @JonashH I removed my comment : you are right for the non atomicity of "index++" – Graffito Apr 05 '23 at 15:26