Re: [RFA 09/11] Use std::set in mi-main.c

Simon Marchi
2017-10-02T13:05:24Z

On 2017-09-28 12:10, Pedro Alves wrote:
> On 09/12/2017 07:57 PM, Tom Tromey wrote:
>> Change a couple of spots in mi-main.c to use std::set. This
>> simplifies the code and removes some cleanups.
>
> std::set always gives me pause. For small objects like int,
> and when the use case is insertion phase + lookup phase + discard set,
> unsorted inserting into a vector, sorting, and then binary searching
> the vector for lookuups is very likely to have better performance, for
> cache locality reasons, and also because fewer allocations (with
> std::set being a node-based container...)
>
> But it's likely that in this case it doesn't really matter, so let's
> go with the simplicity argument.
>
> (At some point I may propose some data structure on top of
> std::vector for use cases like this.)

We have discussed something like this with Sergio in this thread:

https://sourceware.org/ml/gdb-patches/2017-07/msg00434.html

(you can ctrl-f "boilerplate")

We managed to sneak in an std::set while you were not looking/on
vacation :). The idea was that the std::set interface really helped to
keep the code clean and short, and that we could later implement
something with the same behavior and interface as std::set, but based on
a vector. It's a bit different than what you propose, because to be a
drop-in replacement for a set, we would always keep the vector sorted
(insert the new elements where they belong). IIUC, what you propose is
to insert everything and then sort it. I think the latter has a better
worst-case performance (sorting at the end is n*log(n)) compared to the
former (insertion in reverse order will become n^2). I don't think it
matters much though, since this data structure would be explicitly for
relatively small amount of items.

I am not sure if the reasoning is different for a set of string (as in
common/environ.{h,c}). I assume it would be similar, since the actual
string object is rather small, and when inserting a string in the
middle, the following strings will be moved one position and not copied
(I haven't verified though).

Simon