This is the mail archive of the
gdb-patches@sourceware.org
mailing list for the GDB project.
Re: [patch] Performance optimize large bp_location count
- From: Tom Tromey <tromey at redhat dot com>
- To: Jan Kratochvil <jan dot kratochvil at redhat dot com>
- Cc: gdb-patches at sourceware dot org
- Date: Tue, 13 Oct 2009 12:33:59 -0600
- Subject: Re: [patch] Performance optimize large bp_location count
- References: <20090904201706.GA26300@host0.dyn.jankratochvil.net>
- Reply-to: tromey at redhat dot com
>>>>> "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