[patch] Performance optimize large bp_location count
Tom Tromey
tromey@redhat.com
Tue Oct 13 18:34:00 GMT 2009
>>>>> "Jan" == Jan Kratochvil <jan.kratochvil@redhat.com> writes:
Jan> Every breakpoint being inserted runs check_duplicates() which was
Jan> quadratic => the whole operation was cubic. n^3 becomes n^2*log(n)
Jan> by this patch.
n^2*log(n) still seems high, but since it dropped off the profile, then
that is good enough.
I puzzled over the choice of a sorted array here, wondering if there
were perhaps some better data structure. A bit of rationale and
overview in the patch email would go a long way.
Jan> + /* Left boundary, right boundary and media element of our binary search. */
Jan> + unsigned bc_l, bc_r, bc;
I think s/media/median/
Jan> + /* Find BC_L which is a leftmost element which may affect BUF content. It is
Jan> + safe to report lower value but a failure to report higher one. */
Jan> +
Jan> + bc_l = 0;
Jan> + bc_r = bp_location_count;
Jan> + while (bc_l + 1 < bc_r)
Jan> + {
Jan> + struct bp_location *b;
Jan> +
Jan> + bc = (bc_l + bc_r) / 2;
Jan> + b = bp_location[bc];
Jan> +
Jan> + if (b->address + bp_location_shadow_len_after_address_max >= b->address
Jan> + && b->address + bp_location_shadow_len_after_address_max <= memaddr)
Jan> + bc_l = bc;
Jan> + else
Jan> + bc_r = bc;
Jan> + }
It isn't obvious to me why this finds the leftmost element when there
are multiple overlapping ones. What am I missing?
Jan> - cleanups = make_cleanup (do_vec_free, &old_locations);
I think this is the only use of do_vec_free, so that function can be
removed.
Tom
More information about the Gdb-patches
mailing list