Skip to content

Instantly share code, notes, and snippets.

@lpereira

lpereira/gist:4e09f5a038b740d61860488679427c4e

Created September 18, 2017 07:22
Show Gist options
  • Save lpereira/4e09f5a038b740d61860488679427c4e to your computer and use it in GitHub Desktop.
Save lpereira/4e09f5a038b740d61860488679427c4e to your computer and use it in GitHub Desktop.
Download ZIP
Raw
gistfile1.cpp
/* Build with google benchmark */
#include "benchmark/benchmark.h"
#include <ctype.h>
#include <errno.h>
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>
#define ALWAYS_INLINE inline __attribute__((always_inline))
#define LIKELY_IS(x, y) __builtin_expect((x), (y))
#define UNLIKELY(x) LIKELY_IS((x), 0)
#define STRING_SWITCH(s) switch (string_as_int32(s))
#define MULTICHAR_CONSTANT(a, b, c, d) \
((int32_t)((a) | (b) << 8 | (c) << 16 | (d) << 24))
static ALWAYS_INLINE int32_t string_as_int32(const char *s) {
int32_t i;
memcpy(&i, s, sizeof(int32_t));
return i;
}
long parse_long(const char *value, long default_value) {
char *endptr;
long parsed;
errno = 0;
parsed = strtol(value, &endptr, 0);
if (errno != 0)
return default_value;
if (*endptr != '\0' || value == endptr)
return default_value;
return parsed;
}
int parse_int(const char *value, int default_value) {
long long_value = parse_long(value, default_value);
if ((long)(int)long_value != long_value)
return default_value;
return (int)long_value;
}
template <bool ValidateInts>
static int parse_2_digit_num(const char *str, const char end_chr, int min,
int max) {
int val;
if (ValidateInts) {
if (UNLIKELY(!isdigit(*str)))
return -EINVAL;
if (UNLIKELY(!isdigit(*(str + 1))))
return -EINVAL;
if (UNLIKELY(*(str + 2) != end_chr))
return -EINVAL;
}
val = (*str - '0') * 10;
val += *(str + 1) - '0';
if (UNLIKELY(val < min || val > max))
return -EINVAL;
return val;
}
template <bool ValidateInts>
static int parse_4_digit_num(const char *str, const char end_chr) {
int val;
if (ValidateInts) {
if (UNLIKELY(!isdigit(*str)))
return -EINVAL;
if (UNLIKELY(!isdigit(*(str + 1))))
return -EINVAL;
if (UNLIKELY(!isdigit(*(str + 2))))
return -EINVAL;
if (UNLIKELY(!isdigit(*(str + 3))))
return -EINVAL;
if (UNLIKELY(*(str + 4) != end_chr))
return -EINVAL;
}
val = (*str - '0') * 1000;
val += (*(str + 1) - '0') * 100;
val += (*(str + 2) - '0') * 10;
val += *(str + 3) - '0';
return val;
}
template <bool UseTimeGm, bool ValidateInts>
int lwan_parse_rfc_time(const char in[30], time_t *out) {
/* This function is used instead of strptime() because locale
* information can affect the parsing. Instead of defining
* the locale to "C", use hardcoded constants. */
enum {
WEEKDAY_SUN = MULTICHAR_CONSTANT('S', 'u', 'n', ','),
WEEKDAY_MON = MULTICHAR_CONSTANT('M', 'o', 'n', ','),
WEEKDAY_TUE = MULTICHAR_CONSTANT('T', 'u', 'e', ','),
WEEKDAY_WED = MULTICHAR_CONSTANT('W', 'e', 'd', ','),
WEEKDAY_THU = MULTICHAR_CONSTANT('T', 'h', 'u', ','),
WEEKDAY_FRI = MULTICHAR_CONSTANT('F', 'r', 'i', ','),
WEEKDAY_SAT = MULTICHAR_CONSTANT('S', 'a', 't', ','),
MONTH_JAN = MULTICHAR_CONSTANT('J', 'a', 'n', ' '),
MONTH_FEB = MULTICHAR_CONSTANT('F', 'e', 'b', ' '),
MONTH_MAR = MULTICHAR_CONSTANT('M', 'a', 'r', ' '),
MONTH_APR = MULTICHAR_CONSTANT('A', 'p', 'r', ' '),
MONTH_MAY = MULTICHAR_CONSTANT('M', 'a', 'y', ' '),
MONTH_JUN = MULTICHAR_CONSTANT('J', 'u', 'n', ' '),
MONTH_JUL = MULTICHAR_CONSTANT('J', 'u', 'l', ' '),
MONTH_AUG = MULTICHAR_CONSTANT('A', 'u', 'g', ' '),
MONTH_SEP = MULTICHAR_CONSTANT('S', 'e', 'p', ' '),
MONTH_OCT = MULTICHAR_CONSTANT('O', 'c', 't', ' '),
MONTH_NOV = MULTICHAR_CONSTANT('N', 'o', 'v', ' '),
MONTH_DEC = MULTICHAR_CONSTANT('D', 'e', 'c', ' '),
TZ_GMT = MULTICHAR_CONSTANT('G', 'M', 'T', '\0'),
};
struct tm tm;
const char *str = in;
STRING_SWITCH(str) {
case WEEKDAY_SUN:
tm.tm_wday = 0;
break;
case WEEKDAY_MON:
tm.tm_wday = 1;
break;
case WEEKDAY_TUE:
tm.tm_wday = 2;
break;
case WEEKDAY_WED:
tm.tm_wday = 3;
break;
case WEEKDAY_THU:
tm.tm_wday = 4;
break;
case WEEKDAY_FRI:
tm.tm_wday = 5;
break;
case WEEKDAY_SAT:
tm.tm_wday = 6;
break;
default:
return -EINVAL;
}
str += 5;
tm.tm_mday = parse_2_digit_num<ValidateInts>(str, ' ', 1, 31);
if (UNLIKELY(tm.tm_mday < 0))
return -EINVAL;
str += 3;
STRING_SWITCH(str) {
case MONTH_JAN:
tm.tm_mon = 0;
break;
case MONTH_FEB:
tm.tm_mon = 1;
break;
case MONTH_MAR:
tm.tm_mon = 2;
break;
case MONTH_APR:
tm.tm_mon = 3;
break;
case MONTH_MAY:
tm.tm_mon = 4;
break;
case MONTH_JUN:
tm.tm_mon = 5;
break;
case MONTH_JUL:
tm.tm_mon = 6;
break;
case MONTH_AUG:
tm.tm_mon = 7;
break;
case MONTH_SEP:
tm.tm_mon = 8;
break;
case MONTH_OCT:
tm.tm_mon = 9;
break;
case MONTH_NOV:
tm.tm_mon = 10;
break;
case MONTH_DEC:
tm.tm_mon = 11;
break;
default:
return -EINVAL;
}
str += 4;
tm.tm_year = parse_4_digit_num<ValidateInts>(str, ' ');
tm.tm_year -= 1900;
if (ValidateInts) {
if (UNLIKELY(tm.tm_year < 0 || tm.tm_year > 1000))
return -EINVAL;
}
str += 5;
tm.tm_hour = parse_2_digit_num<ValidateInts>(str, ':', 1, 24);
str += 3;
tm.tm_min = parse_2_digit_num<ValidateInts>(str, ':', 1, 59);
str += 3;
tm.tm_sec = parse_2_digit_num<ValidateInts>(str, ' ', 1, 59);
str += 3;
STRING_SWITCH(str) {
case TZ_GMT:
tm.tm_isdst = -1;
if (UseTimeGm) {
*out = timegm(&tm);
if (UNLIKELY(*out == (time_t)-1))
return -EINVAL;
} else {
*out = 0;
}
return 0;
default:
return -EINVAL;
}
}
static const char *dates[] = {
"Fri, 10 Apr 1970 16:37:36 GMT", "Sat, 03 Apr 1976 18:39:45 GMT",
"Mon, 08 Nov 1971 03:57:48 GMT", "Fri, 22 Oct 1971 07:23:07 GMT",
"Tue, 02 Mar 1971 15:08:50 GMT", "Sun, 19 Jan 1992 20:55:52 GMT",
"Fri, 02 Jan 1970 16:51:54 GMT", "Sun, 26 Dec 1993 03:54:16 GMT",
"Mon, 13 Jul 1970 04:27:51 GMT", "Thu, 20 May 1971 01:02:00 GMT",
"Thu, 04 Apr 1985 05:00:00 GMT", "Wed, 25 Aug 1971 22:49:57 GMT",
"Tue, 27 Aug 1974 12:02:04 GMT", "Sun, 21 May 1972 18:28:30 GMT",
"Sun, 13 Nov 1977 12:51:36 GMT", "Tue, 06 Jul 1993 01:57:30 GMT",
"Thu, 01 Dec 1977 19:53:32 GMT", "Fri, 05 Jun 1987 01:55:24 GMT",
"Tue, 20 Jan 1970 09:57:36 GMT", "Thu, 24 Sep 1981 09:19:33 GMT",
"Mon, 28 Dec 1970 21:08:50 GMT", "Tue, 11 Feb 1975 04:40:30 GMT",
"Sat, 04 Sep 1993 04:28:32 GMT", "Fri, 07 Apr 1978 23:27:20 GMT",
"Fri, 25 Nov 1977 12:23:20 GMT", "Tue, 22 Nov 1988 01:30:35 GMT",
"Tue, 08 Feb 1977 04:00:00 GMT", "Sat, 30 May 1987 14:32:30 GMT",
"Fri, 13 Jul 1990 13:15:36 GMT", "Sun, 16 Mar 1975 12:31:53 GMT",
"Fri, 03 Jul 1970 03:26:42 GMT", "Wed, 24 Jan 1973 13:57:24 GMT",
"Thu, 25 Mar 1971 04:42:56 GMT", "Sat, 16 May 1970 08:38:16 GMT",
"Tue, 21 Apr 1970 03:20:43 GMT", "Thu, 06 Oct 1977 03:42:57 GMT",
"Fri, 29 Jun 1973 20:58:06 GMT", "Thu, 10 Nov 1988 11:26:51 GMT",
"Sat, 31 Jan 1970 05:21:04 GMT", "Fri, 05 Aug 1983 07:16:24 GMT",
"Fri, 13 Mar 1970 06:36:40 GMT", "Sun, 04 Apr 1999 14:42:30 GMT",
"Tue, 23 Jan 1973 02:06:45 GMT", "Wed, 15 Sep 1993 04:56:40 GMT",
"Wed, 22 Feb 1978 13:39:35 GMT", "Mon, 08 Nov 1971 16:37:39 GMT",
"Mon, 08 Apr 1985 17:52:12 GMT", "Thu, 28 Mar 1974 02:50:58 GMT",
"Sun, 09 Jun 1974 03:47:47 GMT", "Sat, 25 Sep 1971 11:15:40 GMT",
"Tue, 19 Aug 1975 13:14:21 GMT", "Wed, 26 Nov 1986 18:08:15 GMT",
"Sat, 11 Aug 1973 20:10:48 GMT", "Mon, 26 Jun 1972 23:20:40 GMT",
"Thu, 24 Aug 2000 00:05:57 GMT", "Fri, 03 Sep 1976 15:16:12 GMT",
"Mon, 11 Mar 1991 13:52:48 GMT", "Mon, 10 Dec 1973 11:18:27 GMT",
"Tue, 14 Aug 1973 04:01:12 GMT", "Wed, 19 Mar 1975 06:58:01 GMT",
"Sun, 12 Oct 1975 07:40:54 GMT", "Thu, 29 Dec 1977 17:46:30 GMT",
"Thu, 15 Oct 1987 13:35:44 GMT", "Wed, 04 Mar 1970 10:54:48 GMT",
"Sat, 23 Apr 1977 10:57:18 GMT", "Tue, 20 Sep 1977 16:59:24 GMT",
"Mon, 19 Oct 1981 16:38:15 GMT", "Thu, 25 Feb 1971 06:04:00 GMT",
"Fri, 03 Mar 1995 22:10:48 GMT", "Fri, 07 Dec 1973 04:10:16 GMT",
"Tue, 19 Apr 1983 10:35:31 GMT", "Sat, 17 Jan 1970 14:26:29 GMT",
"Mon, 10 Sep 1973 03:27:49 GMT", "Fri, 26 May 1972 05:41:24 GMT",
"Sat, 22 Mar 1975 00:14:36 GMT", "Tue, 05 Aug 1980 02:08:59 GMT",
"Fri, 20 Feb 1970 22:07:04 GMT", "Fri, 18 Sep 1970 22:15:52 GMT",
"Sat, 21 Jul 1973 06:26:48 GMT", "Sun, 22 Mar 1987 06:40:24 GMT",
"Fri, 30 Mar 1984 23:17:18 GMT", "Sat, 26 Feb 1972 05:04:46 GMT",
"Wed, 12 Apr 1972 18:18:04 GMT", "Thu, 15 Jan 1970 22:59:35 GMT",
"Sun, 26 Aug 1984 19:33:36 GMT", "Fri, 26 Jun 1970 14:38:44 GMT",
"Mon, 28 Aug 1978 23:10:51 GMT", "Fri, 11 Sep 1970 20:20:28 GMT",
"Wed, 15 Mar 1972 09:37:44 GMT", "Sun, 08 Nov 1987 13:32:08 GMT",
"Wed, 19 Dec 1979 11:04:51 GMT", "Thu, 05 Jun 1986 09:49:35 GMT",
"Tue, 10 Sep 1985 15:33:48 GMT", "Mon, 16 Feb 1970 05:06:00 GMT",
"Sun, 10 Sep 1978 04:16:20 GMT", "Sun, 20 Nov 1983 21:40:33 GMT",
"Sat, 10 Jan 1970 19:17:44 GMT", "Wed, 13 Jul 1977 16:28:48 GMT",
"Mon, 02 Dec 1974 08:23:26 GMT", "Sat, 06 Sep 1975 16:03:00 GMT",
};
void BM_strptime_timegm(benchmark::State &state) {
struct tm t;
time_t tt;
int i = 0;
while (state.KeepRunning()) {
benchmark::DoNotOptimize(
strptime(dates[i++ % 100], "%a, %d %b %Y %H:%M:%S GMT", &t));
benchmark::DoNotOptimize(tt = timegm(&t));
}
}
BENCHMARK(BM_strptime_timegm);
void BM_strptime(benchmark::State &state) {
struct tm t;
time_t tt;
int i = 0;
while (state.KeepRunning()) {
benchmark::DoNotOptimize(
strptime(dates[i++ % 100], "%a, %d %b %Y %H:%M:%S GMT", &t));
}
}
BENCHMARK(BM_strptime);
void BM_lwan_timegm(benchmark::State &state) {
time_t t;
int i = 0;
while (state.KeepRunning()) {
benchmark::DoNotOptimize(
lwan_parse_rfc_time<true, false>(dates[i++ % 100], &t));
}
}
BENCHMARK(BM_lwan_timegm);
void BM_lwan(benchmark::State &state) {
time_t t;
int i = 0;
while (state.KeepRunning()) {
benchmark::DoNotOptimize(
lwan_parse_rfc_time<false, false>(dates[i++ % 100], &t));
}
}
BENCHMARK(BM_lwan);
void BM_lwan_validate_int(benchmark::State &state) {
time_t t;
int i = 0;
while (state.KeepRunning()) {
benchmark::DoNotOptimize(
lwan_parse_rfc_time<false, true>(dates[i++ % 100], &t));
}
}
BENCHMARK(BM_lwan_validate_int);
void BM_lwan_timegm_validate_int(benchmark::State &state) {
time_t t;
int i = 0;
while (state.KeepRunning()) {
benchmark::DoNotOptimize(
lwan_parse_rfc_time<true, true>(dates[i++ % 100], &t));
}
}
BENCHMARK(BM_lwan_timegm_validate_int);
BENCHMARK_MAIN()
@lpereira
Copy link
Author

Results on my machine:

2017-09-18 00:24:00
-------------------------------------------------------------------
Benchmark                            Time           CPU Iterations
-------------------------------------------------------------------
BM_strptime_timegm                1220 ns       1218 ns     556654
BM_strptime                       1074 ns       1074 ns     619791
BM_lwan_timegm                      96 ns         96 ns    7417269
BM_lwan                              5 ns          5 ns  128018985
BM_lwan_validate_int                10 ns         10 ns   72639580
BM_lwan_timegm_validate_int         99 ns         99 ns    6726865

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment