[ruby-core:27677] [Feature #2594] 1.8.7 Patch: Reduce time spent in gc.c is_pointer_to_heap().

Issue #2594 has been updated by Kurt  Stephens.


Because the buckets are already sized exponentially decreasing, amortized searches over time becomes O(log(1.8) N) (N = size of heaps[] array) and O(N / 2) =~ O(log N) for N < 8.

In other words it's already O(log(x) N).  The overhead of the binary search algorithm is probably overkill.  Our app only allocates ~8 heaps.  I never seem to allocate more than 9 heaps.

Sorting heaps by address also yields a sort by negative size on Linux x86:

sort_heaps():
heaps[0] => { 0xb4653008, 1102023 }
heaps[1] => { 0xb5b58008, 612235 }
heaps[2] => { 0xb6706008, 340131 }
heaps[3] => { 0xb6d83008, 188962 }
heaps[4] => { 0xb711e008, 104979 }
heaps[5] => { 0xb731f008, 58322 }
heaps[6] => { 0xb743c008, 32401 }
heaps[7] => { 0xb74db008, 18000 }
heaps[8] => { 0xb7533008, 10000 }

We could use an exponential O(1) probe function to map pointers to indexes into the heaps[] table as a function of (ptr - ptr_min) / (ptr_max - ptr_min) and the GROWTH of 1.8:

#define LOMEM ((void*) heaps[0].slot)
#define HIMEM ((void*) (heaps[heaps_used - 1].slot + heaps[heaps_used - 1].limit))
#define GROWTH 1.8

static double
log_heaps_i_probe(void *ptr)
{
  double register t = (double) (ptr - LOMEM) / (double) (HIMEM - LOMEM);
  t = pow(t, GROWTH);
  t *= heaps_used;
  return t;
}

Not exact, but it gets pretty close in O(1) time.:

log_heaps_i_probe():
  ptr 0xb3c9a3d4 => heaps_i = -1 [(nil), 0xa14 ), i_guess => nan
  ptr 0xb414f1f4 => heaps_i = -1 [(nil), 0xa14 ), i_guess => nan
  ptr 0xb4604014 => heaps_i = 0 [0xb4604014, 0xb5b08e4c ), i_guess => 0
  ptr 0xb4ab8e34 => heaps_i = 0 [0xb4604014, 0xb5b08e4c ), i_guess => 0.14264
  ptr 0xb4f6dc54 => heaps_i = 0 [0xb4604014, 0xb5b08e4c ), i_guess => 0.496703
  ptr 0xb5422a74 => heaps_i = 0 [0xb4604014, 0xb5b08e4c ), i_guess => 1.03053
  ptr 0xb58d7894 => heaps_i = 0 [0xb4604014, 0xb5b08e4c ), i_guess => 1.72962
  ptr 0xb5d8c6b4 => heaps_i = 1 [0xb5b09018, 0xb66b6640 ), i_guess => 2.58457
  ptr 0xb62414d4 => heaps_i = 1 [0xb5b09018, 0xb66b6640 ), i_guess => 3.58851
  ptr 0xb66f62f4 => heaps_i = 2 [0xb66b7018, 0xb6d33c70 ), i_guess => 4.73608
  ptr 0xb6bab114 => heaps_i = 2 [0xb66b7018, 0xb6d33c70 ), i_guess => 6.02288
  ptr 0xb705ff34 => heaps_i = 3 [0xb6d34008, 0xb70cea74 ), i_guess => 7.44525
  ptr 0xb7514d54 => heaps_i = -1 [(nil), 0xa14 ), i_guess => 9
  ptr 0xb79c9b74 => heaps_i = -1 [(nil), 0xa14 ), i_guess => 10.6844
  ptr 0xb7e7e994 => heaps_i = -1 [(nil), 0xa14 ), i_guess => 12.4959

A better probe function could be almost exact with a minor up/down scan for misses.  This technique assumes that other routines are not mmap()'ing memory into the [ LOMEM, HIMEM ] area causing holes and discontinuity in the function.

I heard from the REE guys that 1.9 heaps do not grow exponentially, but remain fixed.  In that case a linear O(1) probe function could help find either the min or max index, before doing a binary search.

KAS

----------------------------------------
http://redmine.ruby-lang.org/issues/show/2594

----------------------------------------
http://redmine.ruby-lang.org