Re: [Xen-devel] [PATCH v8.1 15/27] xsplice, symbols: Implement fast symbol names -> virtual addresses lookup

["Jan Beulich" <jbeulich@xxxxxxxx>]

>>> Konrad Rzeszutek Wilk <konrad.wilk@xxxxxxxxxx> 04/14/16 12:02 AM >>>
>NEW CODE:
>
>To make that work we add three tables:

Why three? Two (or a single one with element pairs) ought to be sufficient:
Afaict you could just have (symbol-address,symbol-offset) pairs which you
then sort and search by name (using symbols_expand_symbol() on
symbol-offset, which in turn you store using the result of get_symbol_offset()
during setup of the table).

>1) symbols_addresses_index_sorted[0..symbols_num_syms]. The values are
 >indicies into symbols_addresses array. This is a 1-1 table:
>
 >symbols_addresses_index_sorted:
     >.long   6315
     >.long   6097
>
 >To get the address of a symbol at offset 0 in symbols_name_sorted
 >(see below) we look in symbols_addresses_index_sorted[0] to get
 >6315 and then look in symbols_addresses_index[6315] to find it.
>
>2) The symbols_names_sorted stream - same format as symbols_names but
 >constructued by sorting the <type>[filename#]<symbol> by <symbol>,
 >then [filename#] and lastly type. Recall that symbol_names is sorted
 >based on addresses of the symbols.

Why would you treat the <filename># prefix specially? The full thing is the
symbol you should care about imo.

>3) To make it simpler to search we also add an symbols_markers_sorted
 >array (of size symbols_num_syms/255).

>Searching for symbols is simplified as we can do a binary search
>on symbol_names_sorted (and using symbols_markers_sorted). Since the
>symbols are sorted it takes on average 13 calls to symbols_expand_symbol.
>
>Doing small tests (search for five different symbols) using the old
>and new mechanism show 2ms vs 0ms improvement.

What does "2m vs 0ms" improvement mean here? If you mean to say that on
some symbols there's no gain at all, then I'd question whether millisecond
granularity is enough to see an improvement.

With the basic data question above I'm not going to look at the actual code
for now; I'll leave this until either I understand why the suggested variant
can't work, or until a future version implementing that one.

Jan


_______________________________________________
Xen-devel mailing list
Xen-devel@xxxxxxxxxxxxx
http://lists.xen.org/xen-devel