Making std::list::size() O(1) is a mistake

[Mr Flibble]

Hi!

Making std::list::size() O(1) is a mistake as it breaks std::list::splice;
instead it should be amortized O(1) using, perhaps, mutable
std::optional<std::size_t> for size or such.

Some say nobody cares that I think making std::list::size() O(1) is a
mistake but I am sure others agree with me: the whole point of using
std::list::splice is the performance benefit of manipulating linked lists.

/Flibble

[Bo Persson]

Yes, we know that.

Where were you 15 years ago when this was standardized? Consistency won
over usefulness, and it is a bit late to reverse that now.

Making the size unsigned was also a mistake, but not going to change either.

[Malcolm McLean]

It hardly matters because on modern hardware std::list is almost useless. Even on
tasks which are heavy on inserts / deletes, an std::list is often beaten by an std::vector,
because of a cache issues.

[Öö Tiib]

The std::list that contains large elements is performant for certain usage patterns
and even elegantly so when the algorithm needs its operations that other containers
lack ... like splice, merge, reverse or unique. But in my experience when std::list is
doing well and that matters then boost::intrusive::list is doing even better.

[Bonita Montero]

Am 16.02.2023 um 21:54 schrieb Mr Flibble:

> Hi!
> Making std::list::size() O(1) is a mistake as it breaks std::list::splice;

> ...
You often need list::size() and making it O(N) would hurt more than
counting the items of a splice-operation since this is needed less
frequent.

[Bonita Montero]

Am 17.02.2023 um 11:45 schrieb Malcolm McLean:

> It hardly matters because on modern hardware std::list is almost useless.
> Even on tasks which are heavy on inserts / deletes, an std::list is often
> beaten by an std::vector, because of a cache issues.

std::list makes sense only if you have appends and deletes at the list's
ends and you need to save memory and this is more immportant than the
memory blend of the vector due to its amortized constant overhead inser-
tion propery.

[Paavo Helde]

There are few cases for std::list which I know. One is for holding alive
large entity objects which should not be moved in memory, and another is
for the algorithms which need splice. For the first usage the complexity
of list::size() does not matter, and for the second usage the current
O(1) is counter-productive.

In retrospect, they should have renamed list size() to count() and leave
it O(N). Too late now.

[Bonita Montero]

Am 17.02.2023 um 13:27 schrieb Paavo Helde:

> In retrospect, they should have renamed list size() to count() and leave
> it O(N). Too late now.

No, absolutely not. size() should be O(1) since it is more commonly used
as you might splice.

[Öö Tiib]

Why you repeat same bullshit over? You have zero knowledge what others
use and how frequently and therefore it is not even a lie. For lying you
need at least to think that you know the actual truth.

[Bonita Montero]

Am 17.02.2023 um 13:42 schrieb Öö Tiib:
> On Friday, 17 February 2023 at 14:40:02 UTC+2, Bonita Montero wrote:
>> Am 17.02.2023 um 13:27 schrieb Paavo Helde:
>>
>>> In retrospect, they should have renamed list size() to count() and leave
>>> it O(N). Too late now.
>> No, absolutely not. size() should be O(1) since it is more commonly used
>> as you might splice.
>
> Why you repeat same bullshit over? You have zero knowledge what

> others use and how frequently and therefore it is not even a lie. ...

Idiot.

[Chris Vine]

On Friday, 17 February 2023 at 10:46:02 UTC, Malcolm McLean wrote:
[snip]

> It hardly matters because on modern hardware std::list is almost useless. Even on
> tasks which are heavy on inserts / deletes, an std::list is often beaten by an std::vector,
> because of a cache issues.

Not in the case of queues which might be accessed under thread contention. std::list
and its splice_end() and unsplice_beginning() functions can achieve as close to lock-free
performance as you are going to get with the standard containers, because new nodes
can be constructed outside the queue mutex and all that is done under the mutex is to
swap a few pointers by way of splice and unsplice. Happily splice_end() and
unsplice_beginning() have O(1) complexity irrespective of std::list::size()'s complexity.

[Chris Vine]

On Friday, 17 February 2023 at 19:32:01 UTC, Chris Vine wrote:
> Not in the case of queues which might be accessed under thread contention. std::list
> and its splice_end() and unsplice_beginning() functions can achieve as close to lock-free
> performance as you are going to get with the standard containers, because new nodes
> can be constructed outside the queue mutex and all that is done under the mutex is to
> swap a few pointers by way of splice and unsplice. Happily splice_end() and
> unsplice_beginning() have O(1) complexity irrespective of std::list::size()'s complexity.

My naming could be confusing: by splice_end() I mean an application of std::list::splice
which splices a node into the end of a list, and by unsplice_beginning() I mean an application
of std::list::splice which extracts a node from the beginning of a list.

[Paavo Helde]

By some reason, google returns 0 hits for unsplice_beginning, and only
some non-C++ hits for 'std::list splice_end'.

Anyway, it depends. In std::list each element would be allocated and
released dynamically, which might a bit more expensive than e.g. with
std::deque.

Even though std::deque does not support splicing, the elements can be
moved or swapped into it, and the whole std::deque can be moved or
swapped away by the/a consumer thread. These are also fast operations.
So to me it looks not so guaranteed std::list is definitely a winner for
inter-thread queues. In some cases it might be.

[Chris M. Thomasson]

are you familiar with the following challenge? RCU works nicely. A proxy
collector can work as well.

https://youtu.be/Qxduz-CRnDw

When you get some free time to burn, give it a watch! :^)

[Chris Vine]

On the first point, yes I was using rather unhelpful shorthand which I have since clarified,
taken from some code I use specifically for this purpose,.

On the second point, it is certainly not guaranteed. Cases where a lock-free queue implemented
via CAS work well are the cases where (if you want to use the standard containers instead)
splicing std::list is likely to work well also. For queue elements which are scalars or which have
move operators which don't allocate or deallocate, and enough memory has been reserved,
std::deque or std::vector might be better. The important point where contention is likely is to try
and ensure that allocation and deallocation occur outside the container's mutex.

The argument I refute for this particular case is that "on modern hardware std::list is almost
useless".