Histogram support

1 files changed, 130 insertions, 22 deletions

diff --git a/tools/codegen/core/gen_stats_data.py b/tools/codegen/core/gen_stats_data.py
index c56e1f2608..30e0072eec 100755
--- a/tools/codegen/core/gen_stats_data.py
+++ b/tools/codegen/core/gen_stats_data.py
@@ -47,17 +47,60 @@ for attr in attrs:
 def dbl2u64(d):
   return ctypes.c_ulonglong.from_buffer(ctypes.c_double(d)).value
 
-def shift_works(mapped_bounds, shift_bits):
-  for a, b in zip(mapped_bounds, mapped_bounds[1:]):
+def shift_works_until(mapped_bounds, shift_bits):
+  for i, ab in enumerate(zip(mapped_bounds, mapped_bounds[1:])):
+    a, b = ab
     if (a >> shift_bits) == (b >> shift_bits):
-      return False
-  return True
+      return i
+  return len(mapped_bounds)
 
-def find_max_shift(mapped_bounds):
+def find_ideal_shift(mapped_bounds, max_size):
+  best = None
   for shift_bits in reversed(range(0,64)):
-    if shift_works(mapped_bounds, shift_bits):
-      return shift_bits
-  return -1
+    n = shift_works_until(mapped_bounds, shift_bits)
+    if n == 0: continue
+    table_size = mapped_bounds[n-1] >> shift_bits
+    if table_size > max_size: continue
+    if table_size > 65535: continue
+    if best is None:
+      best = (shift_bits, n, table_size)
+    elif best[1] < n:
+      best = (shift_bits, n, table_size)
+  print best
+  return best
+
+def gen_map_table(mapped_bounds, shift_data):
+  tbl = []
+  cur = 0
+  mapped_bounds = [x >> shift_data[0] for x in mapped_bounds]
+  for i in range(0, mapped_bounds[shift_data[1]-1]):
+    while i > mapped_bounds[cur]:
+      cur += 1
+    tbl.append(mapped_bounds[cur])
+  return tbl
+
+static_tables = []
+
+def decl_static_table(values, type):
+  global static_tables
+  v = (type, values)
+  for i, vp in enumerate(static_tables):
+    if v == vp: return i
+  print "ADD TABLE: %s %r" % (type, values)
+  r = len(static_tables)
+  static_tables.append(v)
+  return r
+
+def type_for_uint_table(table):
+  mv = max(table)
+  if mv < 2**8:
+    return 'uint8_t'
+  elif mv < 2**16:
+    return 'uint16_t'
+  elif mv < 2**32:
+    return 'uint32_t'
+  else:
+    return 'uint64_t'
 
 def gen_bucket_code(histogram):
   bounds = [0, 1]
@@ -75,10 +118,41 @@ def gen_bucket_code(histogram):
       done_trivial = True
       first_nontrivial = len(bounds)
     bounds.append(nextb)
+  bounds_idx = decl_static_table(bounds, 'double')
   if done_trivial:
-    code_bounds = [dbl2u64(x - first_nontrivial) for x in bounds]
-    shift_bits = find_max_shift(code_bounds[first_nontrivial:])
-  print first_nontrivial, shift_bits, bounds, [hex(x >> shift_bits) for x in code_bounds[first_nontrivial:]]
+    first_nontrivial_code = dbl2u64(first_nontrivial)
+    code_bounds = [dbl2u64(x) - first_nontrivial_code for x in bounds]
+    shift_data = find_ideal_shift(code_bounds[first_nontrivial:], 256 * histogram.buckets)
+  print first_nontrivial, shift_data, bounds
+  if shift_data is not None: print [hex(x >> shift_data[0]) for x in code_bounds[first_nontrivial:]]
+  code = 'do {\\\n'
+  code += 'double _hist_val = (double)(value);\\\n'
+  code += 'if (_hist_val < 0) _hist_val = 0;\\\n'
+  code += 'uint64_t _hist_idx = *(uint64_t*)&_hist_val;\\\n'
+  map_table = gen_map_table(code_bounds[first_nontrivial:], shift_data)
+  code += 'gpr_log(GPR_DEBUG, "' + histogram.name + ' %lf %"PRId64 " %"PRId64, _hist_val, _hist_idx, ' + str((map_table[-1] << shift_data[0]) + first_nontrivial_code) + 'ull);\\\n'
+  if first_nontrivial is None:
+    code += ('GRPC_STATS_INC_HISTOGRAM((exec_ctx), GRPC_STATS_HISTOGRAM_%s, (int)_hist_val);\\\n'
+             % histogram.name.upper())
+  else:
+    code += 'if (_hist_val < %f) {\\\n' % first_nontrivial
+    code += ('GRPC_STATS_INC_HISTOGRAM((exec_ctx), GRPC_STATS_HISTOGRAM_%s, (int)_hist_val);\\\n'
+             % histogram.name.upper())
+    code += '} else {'
+    first_nontrivial_code = dbl2u64(first_nontrivial)
+    if shift_data is not None:
+      map_table_idx = decl_static_table(map_table, type_for_uint_table(map_table))
+      code += 'if (_hist_idx < %dull) {\\\n' % ((map_table[-1] << shift_data[0]) + first_nontrivial_code)
+      code += 'GRPC_STATS_INC_HISTOGRAM((exec_ctx), GRPC_STATS_HISTOGRAM_%s, ' % histogram.name.upper()
+      code += 'grpc_stats_table_%d[((_hist_idx - %dull) >> %d)]);\\\n' % (map_table_idx, first_nontrivial_code, shift_data[0])
+      code += '} else {\\\n'
+    code += 'GRPC_STATS_INC_HISTOGRAM((exec_ctx), GRPC_STATS_HISTOGRAM_%s, '% histogram.name.upper()
+    code += 'grpc_stats_histo_find_bucket_slow((exec_ctx), (value), grpc_stats_table_%d, %d));\\\n' % (bounds_idx, len(bounds))
+    if shift_data is not None:
+      code += '}'
+    code += '}'
+  code += '} while (false)'
+  return (code, bounds_idx)
 
 # utility: print a big comment block into a set of files
 def put_banner(files, banner):
@@ -110,6 +184,8 @@ with open('src/core/lib/debug/stats_data.h', 'w') as H:
   print >>H, "#ifndef GRPC_CORE_LIB_DEBUG_STATS_DATA_H"
   print >>H, "#define GRPC_CORE_LIB_DEBUG_STATS_DATA_H"
   print >>H
+  print >>H, "#include <inttypes.h>"
+  print >>H
 
   for typename, instances in sorted(inst_map.items()):
     print >>H, "typedef enum {"
@@ -117,21 +193,41 @@ with open('src/core/lib/debug/stats_data.h', 'w') as H:
       print >>H, "  GRPC_STATS_%s_%s," % (typename.upper(), inst.name.upper())
     print >>H, "  GRPC_STATS_%s_COUNT" % (typename.upper())
     print >>H, "} grpc_stats_%ss;" % (typename.lower())
+    print >>H, "extern const char *grpc_stats_%s_name[GRPC_STATS_%s_COUNT];" % (
+        typename.lower(), typename.upper())
+
+  histo_start = []
+  histo_buckets = []
+  histo_bucket_boundaries = []
+
+  print >>H, "typedef enum {"
+  first_slot = 0
+  for histogram in inst_map['Histogram']:
+    histo_start.append(first_slot)
+    histo_buckets.append(histogram.buckets)
+    print >>H, "  GRPC_STATS_HISTOGRAM_%s_FIRST_SLOT = %d," % (histogram.name.upper(), first_slot)
+    print >>H, "  GRPC_STATS_HISTOGRAM_%s_BUCKETS = %d," % (histogram.name.upper(), histogram.buckets)
+    first_slot += histogram.buckets
+  print >>H, "  GRPC_STATS_HISTOGRAM_BUCKETS = %d" % first_slot
+  print >>H, "} grpc_stats_histogram_constants;"
 
   for ctr in inst_map['Counter']:
     print >>H, ("#define GRPC_STATS_INC_%s(exec_ctx) " +
                 "GRPC_STATS_INC_COUNTER((exec_ctx), GRPC_STATS_COUNTER_%s)") % (
                 ctr.name.upper(), ctr.name.upper())
   for histogram in inst_map['Histogram']:
-    print >>H, ("#define GRPC_STATS_INC_%s(exec_ctx, value) " +
-                "GRPC_STATS_INC_HISTOGRAM((exec_ctx), " +
-                    "GRPC_STATS_HISTOGRAM_%s," +
-                    "%s)") % (
-                histogram.name.upper(),
+    code, bounds_idx = gen_bucket_code(histogram)
+    histo_bucket_boundaries.append(bounds_idx)
+    print >>H, ("#define GRPC_STATS_INC_%s(exec_ctx, value) %s") % (
                 histogram.name.upper(),
-                gen_bucket_code(histogram))
+                code)
 
-  print >>H, "extern const char *grpc_stats_counter_name[GRPC_STATS_COUNTER_COUNT];"
+  for i, tbl in enumerate(static_tables):
+    print >>H, "extern const %s grpc_stats_table_%d[%d];" % (tbl[0], i, len(tbl[1]))
+
+  print >>H, "extern const int grpc_stats_histo_buckets[%d];" % len(inst_map['Histogram'])
+  print >>H, "extern const int grpc_stats_histo_start[%d];" % len(inst_map['Histogram'])
+  print >>H, "extern const double *const grpc_stats_histo_bucket_boundaries[%d];" % len(inst_map['Histogram'])
 
   print >>H
   print >>H, "#endif /* GRPC_CORE_LIB_DEBUG_STATS_DATA_H */"
@@ -156,7 +252,19 @@ with open('src/core/lib/debug/stats_data.c', 'w') as C:
 
   print >>C, "#include \"src/core/lib/debug/stats_data.h\""
 
-  print >>C, "const char *grpc_stats_counter_name[GRPC_STATS_COUNTER_COUNT] = {";
-  for ctr in inst_map['Counter']:
-    print >>C, "  \"%s\"," % ctr.name
-  print >>C, "};"
+  for typename, instances in sorted(inst_map.items()):
+    print >>C, "const char *grpc_stats_%s_name[GRPC_STATS_%s_COUNT] = {" % (
+        typename.lower(), typename.upper())
+    for inst in instances:
+      print >>C, "  \"%s\"," % inst.name
+    print >>C, "};"
+  for i, tbl in enumerate(static_tables):
+    print >>C, "const %s grpc_stats_table_%d[%d] = {%s};" % (
+        tbl[0], i, len(tbl[1]), ','.join('%s' % x for x in tbl[1]))
+
+  print >>C, "const int grpc_stats_histo_buckets[%d] = {%s};" % (
+      len(inst_map['Histogram']), ','.join('%s' % x for x in histo_buckets))
+  print >>C, "const int grpc_stats_histo_start[%d] = {%s};" % (
+      len(inst_map['Histogram']), ','.join('%s' % x for x in histo_start))
+  print >>C, "const double *const grpc_stats_histo_bucket_boundaries[%d] = {%s};" % (
+      len(inst_map['Histogram']), ','.join('grpc_stats_table_%d' % x for x in histo_bucket_boundaries))