Re: [patch] Performance optimize large bp_location count

[Tom Tromey <tromey@redhat.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