Re: [patch 6/6] gdbserver build-id attribute generator

[Jan Kratochvil <jan.kratochvil@redhat.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