This is the mail archive of the
gdb-patches@sourceware.org
mailing list for the GDB project.
Re: [patch 6/6] gdbserver build-id attribute generator
- From: Jan Kratochvil <jan dot kratochvil at redhat dot com>
- To: Aleksandar Ristovski <aristovski at qnx dot com>
- Cc: "gdb-patches at sourceware dot org" <gdb-patches at sourceware dot org>
- Date: Wed, 27 Mar 2013 15:50:28 +0100
- Subject: Re: [patch 6/6] gdbserver build-id attribute generator
- References: <51278984 dot 3070208 at qnx dot com> <20130310210843 dot GG21130 at host2 dot jankratochvil dot net> <514C56D4 dot 1060906 at qnx dot com> <20130326204157 dot GC12291 at host2 dot jankratochvil dot net> <51530465 dot 30503 at qnx dot com>
On Wed, 27 Mar 2013 15:38:29 +0100, Aleksandar Ristovski wrote:
> On 13-03-26 04:41 PM, Jan Kratochvil wrote:
> >>>+ if (build_id_list_p)
> >>>+ qsort (VEC_address (build_id_list_s, data.list),
> >>>+ VEC_length (build_id_list_s, data.list),
> >>>+ sizeof (build_id_list_s), compare_build_id_list);
> >It is always already sorted by Linux kernel, rather a for cycle to verify it
> >really is sorted.
>
> Can we guarantee this is always the case?
Yes.
The problem is that if it is unsorted there is a bug somewhere and that qsort
will hide that bug.
> Even if it is, qsort would
> do similar to what a loop would (i.e. no moves would take place).
(a) qsort has the n*log(n) complexity no matter how sorted the input is.
You are right omitting the read/writes of swapping should speed it up,
just it won't because:
(b) glibc qsort uses msort (=mergesort), therefore it always moves all the
data anyway.
I did not take any benchmarks but I do not think sorted vs. unsorted input
will make any performance difference with glibc.
> I'd leave it with qsort unless you feel strongly about it.
Yes, please change it. It would hide bugs of some unsorted or corrupted data,
and after all it is really needlessly expensive when there are efforts to
optimize the shared libraries reading.
Thanks,
Jan