@@@ adjust bench timings

[mLib] / test / bench.c

/* -*-c-*-
 *
 * Benchmarking support
 *
 * (c) 2023 Straylight/Edgeware
 */

/*----- Licensing notice --------------------------------------------------*
 *
 * This file is part of the mLib utilities library.
 *
 * mLib is free software: you can redistribute it and/or modify it under
 * the terms of the GNU Library General Public License as published by
 * the Free Software Foundation; either version 2 of the License, or (at
 * your option) any later version.
 *
 * mLib is distributed in the hope that it will be useful, but WITHOUT
 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
 * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU Library General Public
 * License for more details.
 *
 * You should have received a copy of the GNU Library General Public
 * License along with mLib.  If not, write to the Free Software
 * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307,
 * USA.
 */

/*----- Header files ------------------------------------------------------*/

#include "config.h"

#include <errno.h>
#include <stdarg.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>

#include "alloc.h"
#include "bench.h"
#include "bits.h"
#include "linreg.h"
#include "macros.h"

/*----- Data structures ---------------------------------------------------*/

struct timer {
  struct bench_timer _t;
  const struct timer_ops *clkops, *cyops;
  union { int fd; } u_cy;
};

struct timer_ops {
  void (*now)(struct bench_time *t_out, struct timer *t);
  void (*teardown)(struct timer *t);
};

/*----- Preliminaries -----------------------------------------------------*/

#define NS_PER_S 1000000000

static void PRINTF_LIKE(1, 2) debug(const char *fmt, ...)
{
  const char *p;
  va_list ap;

  p = getenv("MLIB_BENCH_DEBUG");
  if (p && *p != 'n' && *p != '0') {
    va_start(ap, fmt);
    fputs("mLib BENCH: ", stderr);
    vfprintf(stderr, fmt, ap);
    fputc('\n', stderr);
    va_end(ap);
  }
}

/*----- The null clock ----------------------------------------------------*/

static void null_now(struct bench_time *t_out, struct timer *t) { ; }
static void null_teardown(struct timer *t) { ; }
static const struct timer_ops null_ops = { null_now, null_teardown };

static int null_cyinit(struct timer *t)
  { t->cyops = &null_ops; return (0); }

#define NULL_CYENT { "null", null_cyinit },

/*----- Linux performance counters ----------------------------------------*/

#if defined(HAVE_LINUX_PERF_EVENT_H) && defined(HAVE_UINT64)

#include <sys/types.h>
#include <unistd.h>

#include <linux/perf_event.h>
#include <asm/unistd.h>

static void perfevent_now(struct bench_time *t_out, struct timer *t)
{
  ssize_t n;

  n = read(t->u_cy.fd, &t_out->cy.i, sizeof(t_out->cy.i));
    if (n != sizeof(t_out->cy.i)) {
      debug("failed to read perf-event counter: %s", strerror(errno));
      return;
    }
  t_out->f |= BTF_CYOK;
}

static void perfevent_teardown(struct timer *t)
  { close(t->u_cy.fd); }

static const struct timer_ops perfevent_ops =
  { perfevent_now, perfevent_teardown };

static int perfevent_init(struct timer *t)
{
  struct perf_event_attr attr = { 0 };
  struct bench_time tm;

  attr.type = PERF_TYPE_HARDWARE;
  attr.size = sizeof(attr);
  attr.config = PERF_COUNT_HW_CPU_CYCLES;
  attr.disabled = 0;
  attr.exclude_kernel = 1;
  attr.exclude_hv = 1;

  t->u_cy.fd = syscall(__NR_perf_event_open, &attr, 0, -1, -1, 0);
  if (t->u_cy.fd < 0) {
    debug("couldn't open perf evvent: %s", strerror(errno));
    return (-1);
  }

  tm.f = 0; perfevent_now(&tm, t);
  if (!(tm.f&BTF_CYOK)) { close(t->u_cy.fd); return (-1); }

  t->cyops = &perfevent_ops; return (0);
}
#  define PERFEVENT_CYENT { "linux-perf-event", perfevent_init },
#else
#  define PERFEVENT_CYENT
#endif

/*----- Intel time-stamp counter ------------------------------------------*/

#if defined(__GNUC__) && (defined(__i386__) || defined(__x86_64__))

#define EFLAGS_ID (1u << 21)
#define CPUID_1D_TSC (1u << 4)

static uint32 set_flags(unsigned long m, unsigned long x)
{
  unsigned long r;

#ifdef __x86_64__
#  define TMP "%%rcx"
#else
#  define TMP "%%ecx"
#endif

  __asm__ ("pushf\n\t"
	   "pop %0\n\t"
	   "mov %0, " TMP "\n\t"
	   "and %1, %0\n\t"
	   "xor %2, %0\n\t"
	   "push %0\n\t"
	   "popf\n\t"
	   "pushf\n\t"
	   "pop %0\n\t"
	   "push " TMP "\n\t"
	   "popf"
	   : "=r"(r)
	   : "g"(m), "g"(x)
	   : "ecx");
  return (r);
}

struct cpuid { uint32 a, b, c, d; };

static void cpuid(struct cpuid *info_out, uint32 a, uint32 c)
{
  __asm__ ("movl %1, %%eax\n\t"
	   "movl %2, %%ecx\n\t"
	   "cpuid\n\t"
	   "movl %%eax, 0(%0)\n\t"
	   "movl %%ebx, 4(%0)\n\t"
	   "movl %%ecx, 8(%0)\n\t"
	   "movl %%edx, 12(%0)\n\t"
	   : /* no outputs */
	   : "r"(info_out), "g"(a), "g"(c)
	   : "eax", "ebx", "ecx", "edx", "cc");
}

static void x86rdtsc_now(struct bench_time *t_out, struct timer *t)
{
  uint32 lo, hi;

  __asm__ __volatile__ ("rdtsc" : "=a"(lo), "=d"(hi));
  SET64(t_out->cy, hi, lo); t_out->f |= BTF_CYOK;
}

static const struct timer_ops x86rdtsc_ops =
  { x86rdtsc_now, null_teardown };

static int x86rdtsc_init(struct timer *t)
{
  struct cpuid info;

  if ((set_flags(~EFLAGS_ID, 0)&EFLAGS_ID) ||
      !(set_flags(~EFLAGS_ID, EFLAGS_ID)&EFLAGS_ID))
    { debug("no `cpuid' instruction"); return (-1); }
  cpuid(&info, 0, 0);
  if (info.a < 1) { debug("no `cpuid' leaf 1"); return (-1); }
  cpuid(&info, 1, 0);
  if (!(info.d&CPUID_1D_TSC))
    { debug("no `rdtsc' instrunction"); return (-1); }
  t->cyops = &x86rdtsc_ops; return (0);
}

#  define X86RDTSC_CYENT { "x86-rdtsc", x86rdtsc_init },
#else
#  define X86RDTWC_CYENT
#endif

/*----- POSIX `clock_gettime' ---------------------------------------------*/

#if defined(HAVE_CLOCK_GETTIME) && defined(CLOCK_THREAD_CPUTIME_ID)

static void gettime_now(struct bench_time *t_out, struct timer *t)
{
  struct timespec now;

  if (clock_gettime(CLOCK_THREAD_CPUTIME_ID, &now))
    { debug("error reading POSIX clock: %s", strerror(errno)); return; }
  ASSIGN64(t_out->s, now.tv_sec); t_out->ns = now.tv_nsec;
  t_out->f |= BTF_TIMEOK;
}

static const struct timer_ops gettime_ops = { gettime_now, null_teardown };

static int gettime_init(struct timer *t)
{
  struct bench_time tm;

  tm.f = 0; gettime_now(&tm, t); if (!tm.f&BTF_TIMEOK) return (-1);
  t->clkops = &gettime_ops; return (0);
}

#  define GETTIME_CLKENT { "posix-clock_gettime", gettime_init },
#else
#  define GETTIME_CLKENT
#endif

/*----- Standard C `clock' ------------------------------------------------*/

static void clock_now(struct bench_time *t_out, struct timer *t)
{
  clock_t now, x;
  unsigned long s; uint32 ns;

  now = clock();
    if (now == (clock_t)-1) {
      debug("error reading standard clock: %s", strerror(errno));
      return;
    }
  x = now/CLOCKS_PER_SEC;
    if (x > ULONG_MAX) { debug("standard clock out of range"); return; }

  s = x; x = now - CLOCKS_PER_SEC*s;
  if (!(NS_PER_S%CLOCKS_PER_SEC))
    ns = x*(NS_PER_S/CLOCKS_PER_SEC);
  else if (NS_PER_S <= ULONG_MAX/CLOCKS_PER_SEC)
    ns = (x*NS_PER_S)/CLOCKS_PER_SEC;
  else
    ns = x*((NS_PER_S + 0.0)/CLOCKS_PER_SEC);
  ASSIGN64(t_out->s, s); t_out->ns = ns; t_out->f |= BTF_TIMEOK;
}

static const struct timer_ops clock_ops = { clock_now, null_teardown };

static int clock_init(struct timer *t)
{
  struct bench_time tm;

  tm.f = 0; clock_now(&tm, t); if (!tm.f&BTF_TIMEOK) return (-1);
  t->clkops = &clock_ops; return (0);
}

#define CLOCK_CLKENT { "clock", clock_init },

/*----- Timing setup ------------------------------------------------------*/

static const struct timerent {
  const char *name;
  int (*init)(struct timer */*t*/);
}
  clktab[] = { GETTIME_CLKENT CLOCK_CLKENT { 0, 0 } },
  cytab[] = { PERFEVENT_CYENT X86RDTSC_CYENT NULL_CYENT { 0, 0 } };

static const struct timerent *find_timer_n(const char *name, size_t sz,
					   const struct timerent *timers,
					   const char *what)
{
  while (timers->name) {
    if (strlen(timers->name) == sz && MEMCMP(name, ==, timers->name, sz))
      return (timers);
    timers++;
  }
  debug("%s timer `%.*s' not found", what, (int)sz, name); return (0);
}

static int try_timer(struct timer *t,
		     const struct timerent *timer, const char *what)
{
  if (timer->init(t)) return (-1);
  debug("selected %s timer `%s'", what, timer->name); return (0);
}

static int select_timer(struct timer *t, const struct timerent *timers,
			const char *varname, const char *what)
{
  const char *p; size_t n;
  const struct timerent *timer;

  p = getenv(varname);
  if (!p) {
    while (timers->name)
      if (!try_timer(t, timers++, what)) return (0);
  } else {
    for (;;) {
      n = strcspn(p, ",");
      timer = find_timer_n(p, n, timers, what);
      if (timer && !try_timer(t, timer, what)) return (0);
      if (!p[n]) break;
      p += n + 1;
    }
  }
  debug("no suitable %s timer found", what); return (-1);
}

static void timer_now(struct bench_timer *tm, struct bench_time *t_out)
{
  struct timer *t = (struct timer *)tm;

  t->clkops->now(t_out, t);
  t->cyops->now(t_out, t);
}

static void timer_destroy(struct bench_timer *tm)
{
  struct timer *t = (struct timer *)tm;

  if (!t) return;
  if (t->clkops) t->clkops->teardown(t);
  if (t->cyops) t->cyops->teardown(t);
  xfree(t);
}

static const struct bench_timerops timer_ops = { timer_now, timer_destroy };

struct bench_timer *bench_createtimer(void)
{
  struct timer *t = 0;
  struct bench_timer *ret = 0;

  t = xmalloc(sizeof(*t)); t->cyops = 0; t->clkops = 0;
  if (select_timer(t, clktab, "MLIB_BENCH_CLKTIMER", "clock")) goto end;
  if (select_timer(t, cytab, "MLIB_BENCH_CYCLETIMER", "cycle")) goto end;
  t->_t.ops = &timer_ops; ret = &t->_t; t = 0;
end:
  if (t) timer_destroy(&t->_t);
  return (ret);
}

#ifdef HAVE_UINT64
#  define FLOATK64(k) ((double)(k).i)
#else
#  define FLOATK64(k) ((double)(k).lo + 4275123318.0*(double)(k).hi)
#endif

static void timer_diff(struct bench_timing *delta_out,
		       const struct bench_time *t0,
		       const struct bench_time *t1)
{
  delta_out->f = t0->f&t1->f;
  kludge64 k;

  if (!(delta_out->f&BTF_TIMEOK))
    delta_out->t = 0.0;
  else {
    SUB64(k, t1->s, t0->s);
    delta_out->t = FLOATK64(k) - 1 +
      (t1->ns + NS_PER_S - t0->ns)/(double)NS_PER_S;
  }

  if (!(delta_out->f&BTF_CYOK))
    delta_out->cy = 0.0;
  else {
    SUB64(k, t1->cy, t0->cy);
    delta_out->cy = FLOATK64(k);
  }
}

/*----- Calibration -------------------------------------------------------*/

void bench_init(struct bench_state *b, struct bench_timer *tm)
  { b->tm = tm; b->target_s = 1.0; b->f = 0; }

void bench_destroy(struct bench_state *b)
  { b->tm->ops->destroy(b->tm); }

static void do_nothing(unsigned long n, void *p)
  { while (n--) RELAX; }

int bench_calibrate(struct bench_state *b)
{
  struct linreg lr_clk = LINREG_INIT, lr_cy = LINREG_INIT;
  unsigned long n;
  unsigned i;
  struct bench_timer *tm = b->tm;
  struct bench_time t0, t1;
  struct bench_timing delta;
  bench_fn *fn = LAUNDER(&do_nothing);
  unsigned f = BTF_ANY;
  int rc;

  if (b->f&BTF_ANY) return (0);

  for (i = 0; i < 10; i++)
    { tm->ops->now(tm, &t0); fn(1, 0); tm->ops->now(tm, &t1); }

  debug("calibrating...");
  n = 1;
  for (;;) {
    tm->ops->now(tm, &t0); fn(n, 0); tm->ops->now(tm, &t1);
    timer_diff(&delta, &t0, &t1); f &= delta.f;
    if (!(f&BTF_TIMEOK)) { rc = -1; goto end; }
    linreg_update(&lr_clk, n, delta.t);
    if (!(f&BTF_CYOK))
      debug("  n = %10lu; t = %12g s", n, delta.t);
    else {
      linreg_update(&lr_cy, n, delta.cy);
      debug("  n = %10lu; t = %12g s, cy = %10.0f", n, delta.t, delta.cy);
    }
    if (delta.t >= b->target_s/20.0) break;
    if (n >= ULONG_MAX - n/3) break;
    n += n/3 + 1;
  }

  linreg_fit(&lr_clk, &b->clk.m, &b->clk.c, 0);
  debug("clock overhead = (%g n + %g) s", b->clk.m, b->clk.c);
  if (f&BTF_CYOK) {
    linreg_fit(&lr_clk, &b->clk.m, &b->clk.c, 0);
    debug("cycle overhead = (%g n + %g) cy", b->cy.m, b->cy.c);
  }
  b->f |= f; rc = 0;
end:
  return (rc);
}

int bench_measure(struct bench_timing *t_out, struct bench_state *b,
		  bench_fn *fn, void *p)
{
  struct bench_timer *tm = b->tm;
  struct bench_time t0, t1;
  unsigned long n;

  if (bench_calibrate(b)) return (-1);
  debug("measuring..."); n = 1;
  for (;;) {
    tm->ops->now(tm, &t0); fn(n, p); tm->ops->now(tm, &t1);
    timer_diff(t_out, &t0, &t1);
    if (!(t_out->f&BTF_TIMEOK)) return (-1);
    if (!(t_out->f&BTF_CYOK)) debug("  n = %10lu; t = %12g", n, t_out->t);
    else debug("  n = %10lu; t = %12g, cy = %10.0f", n, t_out->t, t_out->cy);
    if (t_out->t >= 0.72*b->target_s) break;
    n *= 1.44*b->target_s/t_out->t;
  }
  t_out->t -= n*b->clk.m + b->clk.c;
  if (t_out->f&BTF_CYOK) t_out->cy -= n*b->cy.m + b->cy.c;
  if (!(t_out->f&BTF_CYOK)) debug("  adjusted t' = %12g", t_out->t);
  else debug("  adjusted t = %12g, cy = %10.0f", t_out->t, t_out->cy);
  if (!(t_out->f&BTF_CYOK))
    debug("  %g s per op; %g ops/s", t_out->t/n, n/t_out->t);
  else
    debug("  %g s (%g cy) per op; %g ops/s",
	  t_out->t/n, t_out->cy/n, n/t_out->t);
  t_out->n = n; return (0);
}

/*----- That's all, folks -------------------------------------------------*/