This is the mail archive of the gdb-patches@sourceware.org mailing list for the GDB project.


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]
Other format: [Raw text]

Re: [PATCH v2] Implement the ability to set/unset environment variables to GDBserver when starting the inferior


On 2017-08-12 06:33, Sergio Durigan Junior wrote:
Actually, if we expected the user to set thousands of environment
variables and needed it to be fast to set and unset variables, it
would be good to use std::set because of the O(log(N))
lookups/insertions/removals, which matters more when you have a lot of
elements.  But when you just have a few elements, the constant cost is
more significant.  A vector-based set would have O(N) complexity for
these operations (at least for insertions and removals, for lookups it
depends if it is sorted), which would be bad if we had thousands of
elements.  But since we expect to have just a few, it would likely be
faster than std::set's constant cost.

You mean std::vector's constant cost, right?

No, I meant std::set's constant cost, although it wasn't clear. I meant the constant hidden by the big-O notation. The complexity of removing from a set may be O(log(N)), but we could also write it as "C1 * log(N)", where C1 is a constant. For a vector, it would take "C2 * N", where C2 is a constant. If C1 is much larger than C2, then using a set only starts being interesting with large Ns. That does a much better job at explaining than I do:

http://lafstern.org/matt/col1.pdf

Thanks,

Simon


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]