Performance¶
Hashing an image is two steps: decoding the file into pixels, and computing the hash from them. This page shows what each step costs and how both grow with the size of the image, what the settings that make hashing cheaper save, and how to measure on your own machine. Every time on it is measured when the site is built, on the machine named at the foot of the page.
Where the time goes¶
Both steps read every pixel. The decoder produces each one, and the hash converts the image to grayscale and reduces it to its working size, which reads each one again, before the hash proper runs on a few thousand values. One photograph, scaled to six sizes and saved as a JPEG at each, shows how the time follows the number of pixels:
- A hash costs in proportion to the pixels. Twice the pixels, about twice the time: the pass over the full image is all of the cost that grows. mHash also does a fixed amount of work on its 512×512 working image, which is about half of its time on the smallest one.
- Decoding dominates the cheap hashes. aHash, pHash, wHash and BMH share one pass, and take a small part of the decoding time, the smaller the larger the image; dHash, which resamples on its own, about twice theirs.
- mHash, Radial and the color hashes come close to decoding on large images: they blur, sample or count colors at full size. At 20 megapixels Radial takes about as long as the decoding.
- Decoding grows a little faster than the pixel count on this photograph, because the larger JPEGs hold more bytes per pixel (the file sizes are in the table under the next chart): scaling the photograph down averages away fine detail and noise that its full size keeps, and the decoder reads every byte.
Which hash to choose for its cost and what it detects is on Choosing an algorithm.
The numbers behind the chart
One JPEG at six sizes; the minimum of the runs.
| Case | 612×408 | 1225×816 | 1732×1155 | 2739×1826 | 3873×2582 | 5477×3651 |
|---|---|---|---|---|---|---|
| decoding | 0.62 ms | 2.7 ms | 6.1 ms | 18 ms | 43 ms | 105 ms |
| aHash | 0.30 ms | 1.2 ms | 2.3 ms | 5.8 ms | 12 ms | 23 ms |
| dHash | 0.33 ms | 1.3 ms | 2.6 ms | 6.7 ms | 13 ms | 27 ms |
| pHash | 0.31 ms | 1.2 ms | 2.3 ms | 5.8 ms | 12 ms | 23 ms |
| wHash | 0.31 ms | 1.2 ms | 2.3 ms | 5.8 ms | 12 ms | 23 ms |
| mHash | 2.0 ms | 4.6 ms | 8.5 ms | 21 ms | 46 ms | 93 ms |
| BMH | 0.31 ms | 1.2 ms | 2.3 ms | 5.7 ms | 12 ms | 23 ms |
| Radial | 2.0 ms | 6.0 ms | 11 ms | 28 ms | 60 ms | 129 ms |
| ColorHash | 0.38 ms | 1.5 ms | 3.1 ms | 7.8 ms | 16 ms | 31 ms |
| ColorMoments | 0.81 ms | 3.2 ms | 6.5 ms | 17 ms | 33 ms | 66 ms |
How this was measured
The large example photograph, tests/data/photo_large.jpeg, is scaled down with
Pillow's Lanczos filter to each size, keeping its aspect ratio, and saved as a JPEG at
quality 90, a PNG and a WebP at quality 90. Each file is timed by site_stages time,
naming the cases it runs: the load alone, and on the JPEG each hash as the first on the
loaded image. Each case runs once to warm up, then until it has run at least five
times and for at least a second; the time is the minimum.
tools/site/measure/timing.py
# One photograph at several sizes, in megapixels, and in three formats: the large example
# photograph scaled down, keeping its aspect ratio, and encoded the same way at every size,
# so that a time changes with the number of pixels and nothing else. The JPEG is timed
# decoding and hashing; the PNG and the WebP decoding only, as a hash reads the decoded
# pixels whatever the file was.
SIZES_MPX = (0.25, 1, 2, 5, 10, 20)
FORMATS = {"jpeg": ("JPEG", {"quality": 90}), "png": ("PNG", {}),
"webp": ("WEBP", {"quality": 90})}
LOADS = ("decode", "gray_decode")
HASHES = ("ahash", "dhash", "phash", "whash", "bmh", "mhash", "radial", "color_hash",
"color_moments", "multi")
def sized_images():
"""{(mpx, format): path}: the large photograph at each size in each format, written
under build/site-cache/sizes/ once and kept."""
from PIL import Image
source = os.path.join(ROOT, IMAGES["large"])
out_dir = os.path.join(ROOT, "build", "site-cache", "sizes")
os.makedirs(out_dir, exist_ok=True)
paths, image = {}, None
for mpx in SIZES_MPX:
for fmt, (pil, options) in FORMATS.items():
path = os.path.join(out_dir, f"{mpx:g}mpx.{fmt}")
paths[mpx, fmt] = path
if os.path.exists(path):
continue
if image is None:
image = Image.open(source).convert("RGB")
w, h = image.size
scale = (mpx * 1e6 / (w * h)) ** 0.5
size = (round(w * scale), round(h * scale))
image.resize(size, Image.Resampling.LANCZOS).save(path, pil, **options)
return paths
def measure_sizes(tool):
"""{"machine": {...}, "sizes": [{"mpx", "width", "height", "jpeg": {case: ms, "bytes":
the file's size}, "png": {...}, "webp": {...}}]}: the minimum time of each case of `site_stages time` on
the photograph at each size, from the cache when nothing that decides them has changed."""
host = machine()
paths = sized_images()
key = fingerprint(KEY_FILES, [tool] + sorted(paths.values()),
json.dumps(host, sort_keys=True))
def measure():
sizes = []
for mpx in SIZES_MPX:
row = {"mpx": mpx}
for fmt in FORMATS:
cases = LOADS + (HASHES if fmt == "jpeg" else ())
out = json.loads(subprocess.run([tool, "time", paths[mpx, fmt], *cases],
check=True, capture_output=True,
text=True).stdout)
row.update(width=out["width"], height=out["height"])
row[fmt] = {c: v["min_ms"] for c, v in out["cases"].items()}
row[fmt]["bytes"] = os.path.getsize(paths[mpx, fmt])
sizes.append(row)
return {"machine": host, "sizes": sizes}
return cached("timing-sizes", key, measure, "timing by size")
tools/site/stages/timing.c
/* Seconds on a monotonic clock, as tests/src/bench_hash.c reads it. The calendar clock
* (timespec_get() with TIME_UTC) would step back when the system corrects its time, and a
* run spanning the step would come out negative and become the minimum. On Darwin,
* CLOCK_MONOTONIC counts whole microseconds, 2 % of the cheapest hash; mach_absolute_time()
* counts nanoseconds. */
static double seconds(void) {
#ifdef __APPLE__
static mach_timebase_info_data_t tb;
if (tb.denom == 0) {
mach_timebase_info(&tb);
}
return (double)mach_absolute_time() * tb.numer / tb.denom * 1e-9;
#else
struct timespec ts;
clock_gettime(CLOCK_MONOTONIC, &ts);
return (double)ts.tv_sec + (double)ts.tv_nsec * 1e-9;
#endif
}
/* One timed case: `run` does the work once on a loaded image and returns nonzero on
* failure; `arg` selects a variant of it. A case named after an algorithm, or starting
* with its name and "_", is shown on that algorithm's page. */
typedef struct {
const char *name;
int (*run)(ph_context_t *ctx, const char *path, int arg);
int arg;
} time_case_t;
static int time_decode(ph_context_t *ctx, const char *path, int arg) {
(void)arg;
return ph_load_from_file(ctx, path) != PH_SUCCESS;
}
/* The first hash computed on a loaded image, which is what a caller who loads an image
* and hashes it pays: the grayscale conversion and the shared area grid are dropped
* before every run, so each run computes them (the dropping is untimed). */
static int time_hash(ph_context_t *ctx, const char *path, int algo) {
(void)path;
ph_digest_t d;
return ph_compute_digest(ctx, (ph_algorithm_t)algo, &d) != PH_SUCCESS;
}
/* The four 64-bit hashes in one ph_compute_multi() call, which computes the grayscale
* image and the area grid once for all of them. */
static int time_multi(ph_context_t *ctx, const char *path, int arg) {
(void)path;
(void)arg;
uint64_t h[PH_HASH_FLAGS_COUNT];
return ph_compute_multi(ctx, PH_HASH_AHASH | PH_HASH_DHASH | PH_HASH_PHASH | PH_HASH_WHASH,
h) != PH_SUCCESS;
}
static int time_whash_full(ph_context_t *ctx, const char *path, int arg) {
(void)path;
(void)arg;
uint64_t h;
int bad = ph_context_set_whash_mode(ctx, PH_WHASH_FULL) != PH_SUCCESS ||
ph_compute_whash(ctx, &h) != PH_SUCCESS;
return ph_context_set_whash_mode(ctx, PH_WHASH_FAST) != PH_SUCCESS || bad;
}
static int time_mhash_size(ph_context_t *ctx, const char *path, int size) {
(void)path;
ph_digest_t d;
int bad = ph_context_set_mhash_params(ctx, PH_MH_ALPHA, PH_MH_LEVEL, size) != PH_SUCCESS ||
ph_compute_mhash(ctx, &d) != PH_SUCCESS;
return ph_context_set_mhash_params(ctx, PH_MH_ALPHA, PH_MH_LEVEL, PH_MH_IMAGE_SIZE) !=
PH_SUCCESS ||
bad;
}
/* pHash with a dct_size other than the default, and the default block. */
static int time_phash_dct(ph_context_t *ctx, const char *path, int size) {
(void)path;
uint64_t h;
int bad = ph_context_set_phash_params(ctx, size, PH_DCT_REDUCTION_SIZE) != PH_SUCCESS ||
ph_compute_phash(ctx, &h) != PH_SUCCESS;
return ph_context_set_phash_params(ctx, PH_DCT_SIZE, PH_DCT_REDUCTION_SIZE) != PH_SUCCESS ||
bad;
}
/* Radial with the settings of radial_variants[variant]. */
static int time_radial(ph_context_t *ctx, const char *path, int variant) {
(void)path;
ph_digest_t d;
int bad = !radial_settings(ctx, &radial_variants[variant]) ||
ph_compute_radial_hash(ctx, &d) != PH_SUCCESS;
return !radial_settings(ctx, &radial_variants[RADIAL_DEFAULT]) || bad;
}
/* Loading the image, then, unless `algo` is LOAD_ONLY, computing that algorithm: what a
* caller pays for a load and a hash. `arg` packs the load -- a ph_decode_scale_t, plus
* LOAD_GRAY for ph_context_set_load_grayscale() and LOAD_FRESH for a context created and
* freed around the load, as a caller who creates one per image does -- and the algorithm
* above it. Without LOAD_FRESH, a context of its own per kind of load, kept across runs,
* so the cases after it hash the image as it was first loaded. */
enum {
LOAD_GRAY = 4,
LOAD_FRESH = 8,
LOAD_ALGO = 16,
LOAD_ONLY = -1,
};
static int time_load(ph_context_t *ctx, const char *path, int arg) {
(void)ctx;
static ph_context_t *kept[LOAD_FRESH];
int kind = arg % LOAD_FRESH, fresh = arg & LOAD_FRESH, algo = arg / LOAD_ALGO - 1;
ph_context_t *c = fresh ? NULL : kept[kind];
if (!c && ph_create(&c) != PH_SUCCESS) {
return 1;
}
ph_digest_t d;
int bad = ph_context_set_decode_scale(c, (ph_decode_scale_t)(kind & 3)) != PH_SUCCESS ||
ph_context_set_load_grayscale(c, (kind & LOAD_GRAY) != 0) != PH_SUCCESS ||
ph_load_from_file(c, path) != PH_SUCCESS ||
(algo != LOAD_ONLY && ph_compute_digest(c, (ph_algorithm_t)algo, &d) != PH_SUCCESS);
if (fresh) {
ph_free(c);
} else {
kept[kind] = c;
}
return bad;
}
#define LOADED(name, flags, algo) {name, time_load, (flags) + ((algo) + 1) * LOAD_ALGO}
static const time_case_t time_cases[] = {
{"decode", time_decode, 0},
{"ahash", time_hash, PH_ALGO_AHASH},
{"dhash", time_hash, PH_ALGO_DHASH},
{"phash", time_hash, PH_ALGO_PHASH},
{"whash", time_hash, PH_ALGO_WHASH},
{"whash_full", time_whash_full, 0},
{"bmh", time_hash, PH_ALGO_BMH},
{"mhash", time_hash, PH_ALGO_MHASH},
{"radial", time_hash, PH_ALGO_RADIAL},
{"color_hash", time_hash, PH_ALGO_COLOR_HASH},
{"color_moments", time_hash, PH_ALGO_COLOR_MOMENTS},
{"multi", time_multi, 0},
{"mhash_size_62", time_mhash_size, 62},
{"mhash_size_128", time_mhash_size, 128},
{"mhash_size_256", time_mhash_size, 256},
{"mhash_size_512", time_mhash_size, 512},
{"mhash_size_1024", time_mhash_size, 1024},
{"mhash_size_2048", time_mhash_size, 2048},
{"mhash_size_4096", time_mhash_size, 4096},
{"phash_dct_8", time_phash_dct, 8},
{"phash_dct_16", time_phash_dct, 16},
{"phash_dct_24", time_phash_dct, 24},
{"radial_sigma_1", time_radial, RADIAL_SIGMA_1},
{"radial_sigma_8", time_radial, RADIAL_SIGMA_8},
{"radial_gamma_2", time_radial, RADIAL_GAMMA_2},
{"radial_grid_40x32", time_radial, RADIAL_GRID_40X32},
{"radial_grid_90x64", time_radial, RADIAL_GRID_90X64},
{"radial_grid_360x256", time_radial, RADIAL_GRID_360X256},
{"radial_grid_1440x1024", time_radial, RADIAL_GRID_1440X1024},
{"radial_grid_4096x4096", time_radial, RADIAL_GRID_4096X4096},
LOADED("scale_half_decode", PH_DECODE_SCALE_HALF, LOAD_ONLY),
LOADED("scale_quarter_decode", PH_DECODE_SCALE_QUARTER, LOAD_ONLY),
LOADED("scale_eighth_decode", PH_DECODE_SCALE_EIGHTH, LOAD_ONLY),
LOADED("scale_full_phash", PH_DECODE_SCALE_FULL, PH_ALGO_PHASH),
LOADED("scale_half_phash", PH_DECODE_SCALE_HALF, PH_ALGO_PHASH),
LOADED("scale_quarter_phash", PH_DECODE_SCALE_QUARTER, PH_ALGO_PHASH),
LOADED("scale_eighth_phash", PH_DECODE_SCALE_EIGHTH, PH_ALGO_PHASH),
LOADED("scale_full_mhash", PH_DECODE_SCALE_FULL, PH_ALGO_MHASH),
LOADED("scale_half_mhash", PH_DECODE_SCALE_HALF, PH_ALGO_MHASH),
LOADED("scale_quarter_mhash", PH_DECODE_SCALE_QUARTER, PH_ALGO_MHASH),
LOADED("scale_eighth_mhash", PH_DECODE_SCALE_EIGHTH, PH_ALGO_MHASH),
LOADED("scale_full_radial", PH_DECODE_SCALE_FULL, PH_ALGO_RADIAL),
LOADED("scale_half_radial", PH_DECODE_SCALE_HALF, PH_ALGO_RADIAL),
LOADED("scale_quarter_radial", PH_DECODE_SCALE_QUARTER, PH_ALGO_RADIAL),
LOADED("scale_eighth_radial", PH_DECODE_SCALE_EIGHTH, PH_ALGO_RADIAL),
LOADED("gray_decode", LOAD_GRAY, LOAD_ONLY),
LOADED("gray_phash", LOAD_GRAY, PH_ALGO_PHASH),
LOADED("gray_mhash", LOAD_GRAY, PH_ALGO_MHASH),
LOADED("gray_radial", LOAD_GRAY, PH_ALGO_RADIAL),
LOADED("fresh_decode", LOAD_FRESH, LOAD_ONLY),
LOADED("fresh_phash", LOAD_FRESH, PH_ALGO_PHASH),
};
static int cmp_double(const void *a, const void *b) {
double x = *(const double *)a, y = *(const double *)b;
return (x > y) - (x < y);
}
/* One warm-up run, then at least TIME_MIN_RUNS runs and TIME_MIN_SECONDS, at most
* TIME_MAX_RUNS; the minimum is what the pages quote. */
enum {
TIME_MIN_RUNS = 5,
TIME_MAX_RUNS = 300,
};
#define TIME_MIN_SECONDS 1.0
/* Whether case `name` is among the `n` names of `only`; every case is when `n` is 0. */
static int time_chosen(const char *name, int n, char **only) {
for (int i = 0; i < n; i++) {
if (strcmp(name, only[i]) == 0) {
return 1;
}
}
return n == 0;
}
/* site_stages time <image> [case...]: every case of time_cases[] on the image, or the cases
* named; the minimum and the median of its runs, in milliseconds, as one JSON object, with
* the build that ran them. */
int mode_time(int argc, char **argv) {
for (int i = 1; i < argc; i++) {
int known = 0;
for (size_t c = 0; c < COUNT(time_cases); c++) {
known |= strcmp(argv[i], time_cases[c].name) == 0;
}
if (!known) {
return fail("no such timed case", argv[i]);
}
}
ph_context_t *ctx = NULL;
if (load_image(&ctx, argv[0])) {
return 1;
}
json_t j = json_begin(stdout);
json_int(&j, "width", ctx->image.width);
json_int(&j, "height", ctx->image.height);
json_string(&j, "build_info", ph_get_build_info());
#ifdef __VERSION__
json_string(&j, "compiler", __VERSION__);
#endif
json_t cases = json_object(&j, "cases");
static double ms[TIME_MAX_RUNS];
for (size_t c = 0; c < COUNT(time_cases); c++) {
const time_case_t *tc = &time_cases[c];
if (!time_chosen(tc->name, argc - 1, argv + 1)) {
continue;
}
int runs = 0;
double total = 0.0;
for (int k = -1; k < TIME_MAX_RUNS; k++) { /* k = -1: the warm-up */
ph_drop_gray_cache(ctx);
double t0 = seconds();
if (tc->run(ctx, argv[0], tc->arg)) {
ph_free(ctx);
return fail("timed case failed", tc->name);
}
double t = seconds() - t0;
if (k >= 0) {
ms[runs++] = t * 1e3;
total += t;
if (runs >= TIME_MIN_RUNS && total >= TIME_MIN_SECONDS) {
break;
}
}
}
qsort(ms, (size_t)runs, sizeof(ms[0]), cmp_double);
json_t o = json_object(&cases, tc->name);
json_double(&o, "min_ms", ms[0]);
json_double(&o, "median_ms", ms[runs / 2]);
json_int(&o, "runs", runs);
json_close_object(&o);
}
json_close_object(&cases);
json_end(&j);
ph_free(ctx);
return 0;
}
Decoding by format¶
The same photograph decodes at very different speeds as JPEG, PNG and WebP, and asking for grayscale changes the load in a different way for each:
- JPEG is the fastest to decode at every size. PNG takes about twice as long on the largest image and several times as long on the smallest; WebP is the slowest of the three on the large images.
- A grayscale load saves time on a JPEG only. libjpeg-turbo skips its color conversion. The PNG decoder decodes each row in color and folds it to gray as it goes: that takes what the hash's own conversion of a color image would, so the load and the hash together cost the same either way, and the image takes a third of the memory. libwebp has no grayscale output either, and the WebP decoder converts the decoded image the same way (Loading as grayscale).
The decoders themselves depend on the build. The Full build decodes JPEG with libjpeg-turbo, PNG with libpng on zlib-ng and WebP with libwebp; the Minimal build decodes JPEG and PNG with stb_image and has no WebP (Formats and builds). Measured on three platforms, libjpeg-turbo decodes a JPEG to grayscale 1.4 to 6.4 times as fast as stb_image, and libpng on zlib-ng a photographic PNG 1.25 to 1.7 times as fast on Linux (the measurement record). The tables on this site are measured on the Full build.
The numbers behind the chart
One photograph at six sizes, encoded as JPEG (quality 90), PNG and WebP (quality 90); the minimum of the runs.
| Format, load | 612×408 | 1225×816 | 1732×1155 | 2739×1826 | 3873×2582 | 5477×3651 |
|---|---|---|---|---|---|---|
| JPEG, in color | 0.62 ms | 2.7 ms | 6.1 ms | 18 ms | 43 ms | 105 ms |
| JPEG, as grayscale | 0.40 ms | 1.9 ms | 4.5 ms | 15 ms | 36 ms | 83 ms |
| JPEG, bytes per pixel | 0.10 | 0.11 | 0.14 | 0.18 | 0.24 | 0.30 |
| PNG, in color | 2.9 ms | 10 ms | 17 ms | 44 ms | 89 ms | 190 ms |
| PNG, as grayscale | 2.9 ms | 10 ms | 17 ms | 44 ms | 90 ms | 183 ms |
| PNG, bytes per pixel | 0.82 | 0.86 | 0.90 | 1.00 | 1.08 | 1.14 |
| WebP, in color | 1.6 ms | 7.1 ms | 18 ms | 62 ms | 170 ms | 412 ms |
| WebP, as grayscale | 1.6 ms | 7.3 ms | 19 ms | 64 ms | 173 ms | 420 ms |
| WebP, bytes per pixel | 0.05 | 0.06 | 0.10 | 0.17 | 0.23 | 0.30 |
How this was measured
The files of the chart above, timed by the cases decode and gray_decode of
site_stages time: the load in color, and the load with
ph_context_set_load_grayscale(),
each into a context kept from run to run.
tools/site/measure/timing.py
# One photograph at several sizes, in megapixels, and in three formats: the large example
# photograph scaled down, keeping its aspect ratio, and encoded the same way at every size,
# so that a time changes with the number of pixels and nothing else. The JPEG is timed
# decoding and hashing; the PNG and the WebP decoding only, as a hash reads the decoded
# pixels whatever the file was.
SIZES_MPX = (0.25, 1, 2, 5, 10, 20)
FORMATS = {"jpeg": ("JPEG", {"quality": 90}), "png": ("PNG", {}),
"webp": ("WEBP", {"quality": 90})}
LOADS = ("decode", "gray_decode")
HASHES = ("ahash", "dhash", "phash", "whash", "bmh", "mhash", "radial", "color_hash",
"color_moments", "multi")
def sized_images():
"""{(mpx, format): path}: the large photograph at each size in each format, written
under build/site-cache/sizes/ once and kept."""
from PIL import Image
source = os.path.join(ROOT, IMAGES["large"])
out_dir = os.path.join(ROOT, "build", "site-cache", "sizes")
os.makedirs(out_dir, exist_ok=True)
paths, image = {}, None
for mpx in SIZES_MPX:
for fmt, (pil, options) in FORMATS.items():
path = os.path.join(out_dir, f"{mpx:g}mpx.{fmt}")
paths[mpx, fmt] = path
if os.path.exists(path):
continue
if image is None:
image = Image.open(source).convert("RGB")
w, h = image.size
scale = (mpx * 1e6 / (w * h)) ** 0.5
size = (round(w * scale), round(h * scale))
image.resize(size, Image.Resampling.LANCZOS).save(path, pil, **options)
return paths
def measure_sizes(tool):
"""{"machine": {...}, "sizes": [{"mpx", "width", "height", "jpeg": {case: ms, "bytes":
the file's size}, "png": {...}, "webp": {...}}]}: the minimum time of each case of `site_stages time` on
the photograph at each size, from the cache when nothing that decides them has changed."""
host = machine()
paths = sized_images()
key = fingerprint(KEY_FILES, [tool] + sorted(paths.values()),
json.dumps(host, sort_keys=True))
def measure():
sizes = []
for mpx in SIZES_MPX:
row = {"mpx": mpx}
for fmt in FORMATS:
cases = LOADS + (HASHES if fmt == "jpeg" else ())
out = json.loads(subprocess.run([tool, "time", paths[mpx, fmt], *cases],
check=True, capture_output=True,
text=True).stdout)
row.update(width=out["width"], height=out["height"])
row[fmt] = {c: v["min_ms"] for c, v in out["cases"].items()}
row[fmt]["bytes"] = os.path.getsize(paths[mpx, fmt])
sizes.append(row)
return {"machine": host, "sizes": sizes}
return cached("timing-sizes", key, measure, "timing by size")
Making it cheaper¶
Four settings and habits cut the cost, each by a different amount on a different part of it. On a 20-megapixel JPEG, loaded and hashed:
A 5472×3648 JPEG, loaded into a context kept from run to run; the minimum of the runs.
| Load | load + pHash | load + mHash | load + Radial |
|---|---|---|---|
| In color, at full size (the default) | 128 ms | 199 ms | 225 ms |
| As grayscale | 89 ms, −31 % | 157 ms, −21 % | 187 ms, −17 % |
| At ½ size | 90 ms, −30 % | 104 ms, −48 % | 112 ms, −50 % |
| At ¼ size | 79 ms, −38 % | 83 ms, −58 % | 85 ms, −62 % |
| At ⅛ size | 62 ms, −51 % | 64 ms, −68 % | 64 ms, −71 % |
- Decode at a reduced scale.
ph_context_set_decode_scale()decodes a JPEG straight to ½, ¼ or ⅛ of its width and height. The decoding gets only somewhat cheaper, since every coefficient of the file is still read, but everything after it reads a fraction of the pixels: the saving is largest with the hashes that cost the most per pixel. It changes the hash, a little for most algorithms and more for mHash and Radial (Decoding at a reduced scale), and applies to JPEG only. - Load as grayscale, with
ph_context_set_load_grayscale(), when every hash you compute is a grayscale one: on a JPEG, a part of the load is saved. ColorHash and ColorMoments refuse such an image, and on a PNG or a WebP it saves memory, not time (above). -
Compute several hashes from one load. The grayscale image and the area grid that aHash, pHash, wHash and BMH reduce from are computed by the first hash that needs them and kept until the next load (One context, many images), so every hash after the first costs only its own part.
ph_compute_multi()computes the four 64-bit hashes in one call, and costs about half of what the four cost each computed on its own:The minimum of the runs.
Image Decoding aHash + dHash + pHash + wHash, each the first ph_compute_multi(), all four400×400 0.53 ms 0.86 ms 0.31 ms 5472×3648 105 ms 96 ms 32 ms -
Hash many images at once with
ph_hash_files(), which spreads them over a pool of worker threads (Hashing many files).
Creating a context for each image costs nothing measurable beside the load (Loading images has the times), so a context is kept for convenience, not for speed.
How this was measured
Each cell is a case of site_stages time that loads the file into a context kept
from run to run, with the settings of its row, and computes the hash of its column.
The four 64-bit hashes are the cases ahash … whash added up, each the first hash on
a loaded image, against the case multi.
tools/site/pages/performance.py
# The table of what a setting saves: each row a way to load the image, each column the hash
# computed after it, every cell a case of `site_stages time` that loads the file and
# computes that hash.
LEVER_ROWS = (
("In color, at full size (the default)", "scale_full"),
("As grayscale", "gray"),
("At ½ size", "scale_half"),
("At ¼ size", "scale_quarter"),
("At ⅛ size", "scale_eighth"),
)
LEVER_HASHES = ("phash", "mhash", "radial")
# The four 64-bit hashes, each the first on the image, against ph_compute_multi() with
# all four flags.
FOUR = ("ahash", "dhash", "phash", "whash")
tools/site/stages/timing.c
/* Seconds on a monotonic clock, as tests/src/bench_hash.c reads it. The calendar clock
* (timespec_get() with TIME_UTC) would step back when the system corrects its time, and a
* run spanning the step would come out negative and become the minimum. On Darwin,
* CLOCK_MONOTONIC counts whole microseconds, 2 % of the cheapest hash; mach_absolute_time()
* counts nanoseconds. */
static double seconds(void) {
#ifdef __APPLE__
static mach_timebase_info_data_t tb;
if (tb.denom == 0) {
mach_timebase_info(&tb);
}
return (double)mach_absolute_time() * tb.numer / tb.denom * 1e-9;
#else
struct timespec ts;
clock_gettime(CLOCK_MONOTONIC, &ts);
return (double)ts.tv_sec + (double)ts.tv_nsec * 1e-9;
#endif
}
/* One timed case: `run` does the work once on a loaded image and returns nonzero on
* failure; `arg` selects a variant of it. A case named after an algorithm, or starting
* with its name and "_", is shown on that algorithm's page. */
typedef struct {
const char *name;
int (*run)(ph_context_t *ctx, const char *path, int arg);
int arg;
} time_case_t;
static int time_decode(ph_context_t *ctx, const char *path, int arg) {
(void)arg;
return ph_load_from_file(ctx, path) != PH_SUCCESS;
}
/* The first hash computed on a loaded image, which is what a caller who loads an image
* and hashes it pays: the grayscale conversion and the shared area grid are dropped
* before every run, so each run computes them (the dropping is untimed). */
static int time_hash(ph_context_t *ctx, const char *path, int algo) {
(void)path;
ph_digest_t d;
return ph_compute_digest(ctx, (ph_algorithm_t)algo, &d) != PH_SUCCESS;
}
/* The four 64-bit hashes in one ph_compute_multi() call, which computes the grayscale
* image and the area grid once for all of them. */
static int time_multi(ph_context_t *ctx, const char *path, int arg) {
(void)path;
(void)arg;
uint64_t h[PH_HASH_FLAGS_COUNT];
return ph_compute_multi(ctx, PH_HASH_AHASH | PH_HASH_DHASH | PH_HASH_PHASH | PH_HASH_WHASH,
h) != PH_SUCCESS;
}
static int time_whash_full(ph_context_t *ctx, const char *path, int arg) {
(void)path;
(void)arg;
uint64_t h;
int bad = ph_context_set_whash_mode(ctx, PH_WHASH_FULL) != PH_SUCCESS ||
ph_compute_whash(ctx, &h) != PH_SUCCESS;
return ph_context_set_whash_mode(ctx, PH_WHASH_FAST) != PH_SUCCESS || bad;
}
static int time_mhash_size(ph_context_t *ctx, const char *path, int size) {
(void)path;
ph_digest_t d;
int bad = ph_context_set_mhash_params(ctx, PH_MH_ALPHA, PH_MH_LEVEL, size) != PH_SUCCESS ||
ph_compute_mhash(ctx, &d) != PH_SUCCESS;
return ph_context_set_mhash_params(ctx, PH_MH_ALPHA, PH_MH_LEVEL, PH_MH_IMAGE_SIZE) !=
PH_SUCCESS ||
bad;
}
/* pHash with a dct_size other than the default, and the default block. */
static int time_phash_dct(ph_context_t *ctx, const char *path, int size) {
(void)path;
uint64_t h;
int bad = ph_context_set_phash_params(ctx, size, PH_DCT_REDUCTION_SIZE) != PH_SUCCESS ||
ph_compute_phash(ctx, &h) != PH_SUCCESS;
return ph_context_set_phash_params(ctx, PH_DCT_SIZE, PH_DCT_REDUCTION_SIZE) != PH_SUCCESS ||
bad;
}
/* Radial with the settings of radial_variants[variant]. */
static int time_radial(ph_context_t *ctx, const char *path, int variant) {
(void)path;
ph_digest_t d;
int bad = !radial_settings(ctx, &radial_variants[variant]) ||
ph_compute_radial_hash(ctx, &d) != PH_SUCCESS;
return !radial_settings(ctx, &radial_variants[RADIAL_DEFAULT]) || bad;
}
/* Loading the image, then, unless `algo` is LOAD_ONLY, computing that algorithm: what a
* caller pays for a load and a hash. `arg` packs the load -- a ph_decode_scale_t, plus
* LOAD_GRAY for ph_context_set_load_grayscale() and LOAD_FRESH for a context created and
* freed around the load, as a caller who creates one per image does -- and the algorithm
* above it. Without LOAD_FRESH, a context of its own per kind of load, kept across runs,
* so the cases after it hash the image as it was first loaded. */
enum {
LOAD_GRAY = 4,
LOAD_FRESH = 8,
LOAD_ALGO = 16,
LOAD_ONLY = -1,
};
static int time_load(ph_context_t *ctx, const char *path, int arg) {
(void)ctx;
static ph_context_t *kept[LOAD_FRESH];
int kind = arg % LOAD_FRESH, fresh = arg & LOAD_FRESH, algo = arg / LOAD_ALGO - 1;
ph_context_t *c = fresh ? NULL : kept[kind];
if (!c && ph_create(&c) != PH_SUCCESS) {
return 1;
}
ph_digest_t d;
int bad = ph_context_set_decode_scale(c, (ph_decode_scale_t)(kind & 3)) != PH_SUCCESS ||
ph_context_set_load_grayscale(c, (kind & LOAD_GRAY) != 0) != PH_SUCCESS ||
ph_load_from_file(c, path) != PH_SUCCESS ||
(algo != LOAD_ONLY && ph_compute_digest(c, (ph_algorithm_t)algo, &d) != PH_SUCCESS);
if (fresh) {
ph_free(c);
} else {
kept[kind] = c;
}
return bad;
}
#define LOADED(name, flags, algo) {name, time_load, (flags) + ((algo) + 1) * LOAD_ALGO}
static const time_case_t time_cases[] = {
{"decode", time_decode, 0},
{"ahash", time_hash, PH_ALGO_AHASH},
{"dhash", time_hash, PH_ALGO_DHASH},
{"phash", time_hash, PH_ALGO_PHASH},
{"whash", time_hash, PH_ALGO_WHASH},
{"whash_full", time_whash_full, 0},
{"bmh", time_hash, PH_ALGO_BMH},
{"mhash", time_hash, PH_ALGO_MHASH},
{"radial", time_hash, PH_ALGO_RADIAL},
{"color_hash", time_hash, PH_ALGO_COLOR_HASH},
{"color_moments", time_hash, PH_ALGO_COLOR_MOMENTS},
{"multi", time_multi, 0},
{"mhash_size_62", time_mhash_size, 62},
{"mhash_size_128", time_mhash_size, 128},
{"mhash_size_256", time_mhash_size, 256},
{"mhash_size_512", time_mhash_size, 512},
{"mhash_size_1024", time_mhash_size, 1024},
{"mhash_size_2048", time_mhash_size, 2048},
{"mhash_size_4096", time_mhash_size, 4096},
{"phash_dct_8", time_phash_dct, 8},
{"phash_dct_16", time_phash_dct, 16},
{"phash_dct_24", time_phash_dct, 24},
{"radial_sigma_1", time_radial, RADIAL_SIGMA_1},
{"radial_sigma_8", time_radial, RADIAL_SIGMA_8},
{"radial_gamma_2", time_radial, RADIAL_GAMMA_2},
{"radial_grid_40x32", time_radial, RADIAL_GRID_40X32},
{"radial_grid_90x64", time_radial, RADIAL_GRID_90X64},
{"radial_grid_360x256", time_radial, RADIAL_GRID_360X256},
{"radial_grid_1440x1024", time_radial, RADIAL_GRID_1440X1024},
{"radial_grid_4096x4096", time_radial, RADIAL_GRID_4096X4096},
LOADED("scale_half_decode", PH_DECODE_SCALE_HALF, LOAD_ONLY),
LOADED("scale_quarter_decode", PH_DECODE_SCALE_QUARTER, LOAD_ONLY),
LOADED("scale_eighth_decode", PH_DECODE_SCALE_EIGHTH, LOAD_ONLY),
LOADED("scale_full_phash", PH_DECODE_SCALE_FULL, PH_ALGO_PHASH),
LOADED("scale_half_phash", PH_DECODE_SCALE_HALF, PH_ALGO_PHASH),
LOADED("scale_quarter_phash", PH_DECODE_SCALE_QUARTER, PH_ALGO_PHASH),
LOADED("scale_eighth_phash", PH_DECODE_SCALE_EIGHTH, PH_ALGO_PHASH),
LOADED("scale_full_mhash", PH_DECODE_SCALE_FULL, PH_ALGO_MHASH),
LOADED("scale_half_mhash", PH_DECODE_SCALE_HALF, PH_ALGO_MHASH),
LOADED("scale_quarter_mhash", PH_DECODE_SCALE_QUARTER, PH_ALGO_MHASH),
LOADED("scale_eighth_mhash", PH_DECODE_SCALE_EIGHTH, PH_ALGO_MHASH),
LOADED("scale_full_radial", PH_DECODE_SCALE_FULL, PH_ALGO_RADIAL),
LOADED("scale_half_radial", PH_DECODE_SCALE_HALF, PH_ALGO_RADIAL),
LOADED("scale_quarter_radial", PH_DECODE_SCALE_QUARTER, PH_ALGO_RADIAL),
LOADED("scale_eighth_radial", PH_DECODE_SCALE_EIGHTH, PH_ALGO_RADIAL),
LOADED("gray_decode", LOAD_GRAY, LOAD_ONLY),
LOADED("gray_phash", LOAD_GRAY, PH_ALGO_PHASH),
LOADED("gray_mhash", LOAD_GRAY, PH_ALGO_MHASH),
LOADED("gray_radial", LOAD_GRAY, PH_ALGO_RADIAL),
LOADED("fresh_decode", LOAD_FRESH, LOAD_ONLY),
LOADED("fresh_phash", LOAD_FRESH, PH_ALGO_PHASH),
};
static int cmp_double(const void *a, const void *b) {
double x = *(const double *)a, y = *(const double *)b;
return (x > y) - (x < y);
}
/* One warm-up run, then at least TIME_MIN_RUNS runs and TIME_MIN_SECONDS, at most
* TIME_MAX_RUNS; the minimum is what the pages quote. */
enum {
TIME_MIN_RUNS = 5,
TIME_MAX_RUNS = 300,
};
#define TIME_MIN_SECONDS 1.0
/* Whether case `name` is among the `n` names of `only`; every case is when `n` is 0. */
static int time_chosen(const char *name, int n, char **only) {
for (int i = 0; i < n; i++) {
if (strcmp(name, only[i]) == 0) {
return 1;
}
}
return n == 0;
}
/* site_stages time <image> [case...]: every case of time_cases[] on the image, or the cases
* named; the minimum and the median of its runs, in milliseconds, as one JSON object, with
* the build that ran them. */
int mode_time(int argc, char **argv) {
for (int i = 1; i < argc; i++) {
int known = 0;
for (size_t c = 0; c < COUNT(time_cases); c++) {
known |= strcmp(argv[i], time_cases[c].name) == 0;
}
if (!known) {
return fail("no such timed case", argv[i]);
}
}
ph_context_t *ctx = NULL;
if (load_image(&ctx, argv[0])) {
return 1;
}
json_t j = json_begin(stdout);
json_int(&j, "width", ctx->image.width);
json_int(&j, "height", ctx->image.height);
json_string(&j, "build_info", ph_get_build_info());
#ifdef __VERSION__
json_string(&j, "compiler", __VERSION__);
#endif
json_t cases = json_object(&j, "cases");
static double ms[TIME_MAX_RUNS];
for (size_t c = 0; c < COUNT(time_cases); c++) {
const time_case_t *tc = &time_cases[c];
if (!time_chosen(tc->name, argc - 1, argv + 1)) {
continue;
}
int runs = 0;
double total = 0.0;
for (int k = -1; k < TIME_MAX_RUNS; k++) { /* k = -1: the warm-up */
ph_drop_gray_cache(ctx);
double t0 = seconds();
if (tc->run(ctx, argv[0], tc->arg)) {
ph_free(ctx);
return fail("timed case failed", tc->name);
}
double t = seconds() - t0;
if (k >= 0) {
ms[runs++] = t * 1e3;
total += t;
if (runs >= TIME_MIN_RUNS && total >= TIME_MIN_SECONDS) {
break;
}
}
}
qsort(ms, (size_t)runs, sizeof(ms[0]), cmp_double);
json_t o = json_object(&cases, tc->name);
json_double(&o, "min_ms", ms[0]);
json_double(&o, "median_ms", ms[runs / 2]);
json_int(&o, "runs", runs);
json_close_object(&o);
}
json_close_object(&cases);
json_end(&j);
ph_free(ctx);
return 0;
}
One image, one thread¶
Parallelism is across images only: the threads of a batch sizes its pool of workers and
nothing else. A single image, in a batch worker or through a direct
ph_load_from_file() and ph_compute_*() call, is
decoded, converted to grayscale and hashed on the calling thread.
Splitting one image across threads would buy little where the time goes.
On the 5472×3648 JPEG, decoding is 77 % of a load followed by ph_compute_multi() with all four flags.
Neither libjpeg-turbo nor libpng splits one decode across threads, so only the hash would be split. It would also oversubscribe the machine whenever a batch already runs a worker per CPU, which is why libwebp's optional second decoding thread is left off as well. A program with one large JPEG and idle cores gains more from decoding it at a reduced scale.
Measuring on your machine¶
bench_hash times decoding and hashing on any image, as the minimum, median and 90th
percentile of its runs. The minimum is the number to compare between two builds: the
others move with whatever else the machine is doing. CMake builds it with the tests:
cmake --preset release && cmake --build --preset release --target bench_hash
build/release/bench_hash hash photo.jpg 100 # every hash, the first on the image
build/release/bench_hash load photo.jpg 100 3 # loading in color and as grayscale, at ⅛
build/release/bench_hash full photo.jpg 100 # a load and pHash, together
build/release/bench_hash --json hash photo.jpg # the same, as JSON
make benchmark builds and runs it from the Makefile, whose build decodes with stb_image:
its times are those of the Minimal build. The tables on this page are rebuilt by
make site, which runs site_stages time on the files above.
-
Measured when this site was built, on Intel(R) Xeon(R) Platinum 8370C CPU @ 2.80GHz, 4 cores, Linux x86_64; compiled by 13.3.0, optimized, with libjpeg-turbo decoding the JPEGs: the minimum of at least five runs after a warm-up. What each time covers, and the code, are under “How this was measured” beside it. ↩