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

[Simon Marchi <simon dot marchi at polymtl dot ca>]

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