TryTake is stealing an element that was added least recently on another thread

Question

While explaining the ConcurrentBag<T>, The online link says that:

...So, to be precise, calling Take gives you the element added most recently on that thread; if there are no elements on that thread, it gives you the element added most recently on another thread, chosen at random.

In fact, in VS, if you deep down, you'll see this comment for the TrySteal method(TryTake internally calls this method):

If there's no local queue for this thread, just start from the head queue and try to steal from each queue until we get a result. If there is a local queue from this thread, then start from the next queue after it, and then iterate around back from the head to this queue, not including it.

Now let me show you the following program:

using static System.Console;
using System.Collections.Concurrent;

IProducerConsumerCollection<Car> cars = new ConcurrentBag<Car>();

var addBlackCars = Task.Run(ProcessBlackCarModels);
var addNonBlackCars = Task.Run(ProcessNonBlackCarModels);
Task.WaitAll(addBlackCars, addNonBlackCars);
WriteLine($"At present, the repository contains {cars.Count} car(s).");
void ProcessNonBlackCarModels()
{
    Car car;
    car = new("Hyundai Creta", "Pearl");
    WriteLine($"Adding: {car} using task-{Task.CurrentId}");
    cars.TryAdd(car);
    Thread.Sleep(1000);

    car = new("Maruti Suzuki Alto 800", "Red");
    WriteLine($"Adding: {car} using task-{Task.CurrentId}");
    cars.TryAdd(car);
    Thread.Sleep(1000);

    car = new("Toyota Fortuner Avant", "Bronze");
    WriteLine($"Adding: {car} using task-{Task.CurrentId}");
    cars.TryAdd(car);
    Thread.Sleep(1000);

    WriteLine($"Task-{Task.CurrentId} will try removing one item now.");
    if (cars.Count > 0)
    {
        cars.TryTake(out Car removeCar);
        WriteLine($"Tried removing: {removeCar} using task-{Task.CurrentId}");
    }
}

void ProcessBlackCarModels()
{
    Car car;
    car = new("Toyota Fortuner Attitude", "Black");
    WriteLine($"Adding: {car} using task-{Task.CurrentId}");
    cars.TryAdd(car);
    Thread.Sleep(1000);

    car = new("Hyundai Creta Abyss", "Black");
    WriteLine($"Adding: {car} using task-{Task.CurrentId}");
    cars.TryAdd(car);


    // Putting a relatively long sleep so that the other task can finish in between.
    Thread.Sleep(5000);

    WriteLine($"Task-{Task.CurrentId} will try removing three items now.");

    for (int i = 0; i < 3; i++)
    {
        if (cars.Count > 0)
         {
            cars.TryTake(out Car removeCar);
            WriteLine($"Tried removing: {removeCar} using task-{Task.CurrentId}");
        }
    } 

}

// Using primary constructor
class Car(string model, string color)
{
    private string _model = model;
    private string _color = color;

    public override string ToString()
    {
        return $"[{_model}, {_color}]";
    }
}

Here is a sample output:

Adding: [Toyota Fortuner Attitude, Black] using task-1
Adding: [Hyundai Creta, Pearl] using task-2
Adding: [Maruti Suzuki Alto 800, Red] using task-2
Adding: [Hyundai Creta Abyss, Black] using task-1
Adding: [Toyota Fortuner Avant, Bronze] using task-2
Task-2 will try removing one item now.
Tried removing: [Toyota Fortuner Avant, Bronze] using task-2
Task-1 will try removing three items now.
Tried removing: [Hyundai Creta Abyss, Black] using task-1
Tried removing: [Toyota Fortuner Attitude, Black] using task-1
Tried removing: [Hyundai Creta, Pearl] using task-1
At present, the repository contains 1 car(s).

Notice that task-1 needed to steal the 3rd item in this output and it does this by removing the item that was added by task-2 at the beginning i.e. it was least recently added.

My understanding was: task-1 was supposed to remove the item by task-2 which was most recently added, but not the least recently added. Please help me to correct this understanding.

Answer 1

While Joseph Albahari's "Threading in C#" is a great read but you should note that 1) the order is not fixed in the documentation and is an implementation detail 2) the original article was written quite long ago in .NET Framework times.

Based on the source code for .NET Frameworks's implementation it could have been changed since the book was written (or maybe the author got it wrong). If I'm understanding correctly - items are added to the head of the linked list (i.e. new item becomes new head, naming is a bit confusing) - source and are removed from the tail when stealing (source):

/// <summary>
/// Steal an item from the tail of the list
/// </summary>
/// <param name="result">the removed item</param>
/// <param name="remove">remove or peek flag</param>
internal void Steal(out T result, bool remove)  

And 4.7.2 repro behaves in the LIFO way for stealing - demo @dotnetfiddle.

And the current implementation adds to the tail of the queue and steals from the head:

/// <summary>Steal an item from the head of the queue.</summary>
/// <param name="result">the removed item</param>
/// <param name="take">true to take the item; false to simply peek at it</param>
internal bool TrySteal([MaybeNullWhen(false)] out T result, bool take)

Resulting in the same behavior as you observed (demo @dotnetfiddle)