RE: [PATCH v3 3/8] btrace: Use binary search to find instruction.

["Metzger, Markus T" <markus dot t dot metzger at intel dot com>]

> -----Original Message-----
> From: Wiederhake, Tim
> Sent: Monday, November 21, 2016 4:49 PM
> To: gdb-patches@sourceware.org
> Cc: palves@redhat.com; Metzger, Markus T <markus.t.metzger@intel.com>
> Subject: [PATCH v3 3/8] btrace: Use binary search to find instruction.
> 
> Currently, btrace_find_insn_by_number will iterate over all function call
> segments to find the one that contains the needed instruction.  This linear
> search is too slow for the upcoming Python bindings that will use this
> function to access instructions.  This patch introduces a vector in struct
> btrace_thread_info that holds pointers to all recorded function segments and
> allows to use binary search.
> 
> The proper solution is to turn the underlying tree into a vector of objects
> and use indices for access.  This requires more work.  A patch set is
> currently being worked on and will be published later.
> 
> 2016-11-21  Tim Wiederhake  <tim.wiederhake@intel.com>
> 
> gdb/ChangeLog:
> 	* btrace.c (btrace_fetch): Copy function call segments pointer
> 	into a vector.
> 	(btrace_clear): Clear the vector.
> 	(btrace_find_insn_by_number): Use binary search to find the correct
> 	function call segment.
> 	* btrace.h (brace_fun_p): New typedef.
> 	(struct btrace_thread_info) <functions>: New field.


> -  if (bfun == NULL)
> +  lower = 0;
> +  bfun = VEC_index (btrace_fun_p, btinfo->functions, lower);
> +  if (number < bfun->insn_offset)
>      return 0;
> 
> -  if (bfun->insn_offset + ftrace_call_num_insn (bfun) <= number)
> +  upper = VEC_length (btrace_fun_p, btinfo->functions) - 1;
> +  bfun = VEC_index (btrace_fun_p, btinfo->functions, upper);
> +  if (number >= bfun->insn_offset + ftrace_call_num_insn (bfun))
>      return 0;
> 
> +  average = lower + (upper - lower) / 2;
> +  bfun = VEC_index (btrace_fun_p, btinfo->functions, average);
> +
> +  while ((number >= bfun->insn_offset + ftrace_call_num_insn (bfun))
> +      || (number < bfun->insn_offset))
> +    {
> +      if (number < bfun->insn_offset)
> +	upper = average - 1;
> +      else
> +	lower = average + 1;
> +
> +      average = lower + (upper - lower) / 2;
> +      bfun = VEC_index (btrace_fun_p, btinfo->functions, average);
> +    }
> +
>    it->function = bfun;
>    it->index = number - bfun->insn_offset;

This could be simplified a bit.  Instead of checking the very small (i.e. zero
in practice) and very big numbers upfront, we can let them fall through the
binary search loop - both cases are unlikely.

Also the loop could be simplified by merging the termination check and the
check in the loop body so we end up with only one of the checks for low
numbers.

The algorithm looks good, however, and IIUC we're going to change that
again with an in-progress patch series.  So we might as well leave it as-is
and consider this in the final version.


Looks good to me.

Thanks,
Markus.

Intel Deutschland GmbH
Registered Address: Am Campeon 10-12, 85579 Neubiberg, Germany
Tel: +49 89 99 8853-0, www.intel.de
Managing Directors: Christin Eisenschmid, Christian Lamprechter
Chairperson of the Supervisory Board: Nicole Lau
Registered Office: Munich
Commercial Register: Amtsgericht Muenchen HRB 186928