Skip to content

Instantly share code, notes, and snippets.

@benibela
Created March 28, 2020 21:12
Show Gist options
  • Save benibela/f7f1f4d6ba04a0f84045b77904306c75 to your computer and use it in GitHub Desktop.
Save benibela/f7f1f4d6ba04a0f84045b77904306c75 to your computer and use it in GitHub Desktop.
Case vs. hashset benchmark
program benchmark;
{$mode objfpc}{$H+}
uses
{$IFDEF UNIX}{$IFDEF UseCThreads}
cthreads,
{$ENDIF}{$ENDIF}
Classes, xquery.internals.common, bbutils, bbdebugtools,htmlInformation, SysUtils
{ you can add units after this };
//{$define K3}
//{$define K6}
//{$define K9}
{$define K15}
{$ifdef K3}{$define K3P}{$endif}
{$ifdef K6}{$define K3P}{$define K6P}{$endif}
{$ifdef K9}{$define K3P}{$define K6P}{$define K9P}{$endif}
{$ifdef K12}{$define K3P}{$define K6P}{$define K9P}{$define K12P}{$endif}
{$ifdef K15}{$define K3P}{$define K6P}{$define K9P}{$define K12P}{$define K15P}{$endif}
const n = 10000000;
k = {$ifdef K3}3{$endif}{$ifdef K6}6{$endif}{$ifdef K9}9{$endif}{$ifdef K12}12{$endif}{$ifdef K15}15{$endif};
nomatchfiller = 5;
type HTMLNodeNameHashs = object
const img = $4FACAFC2;
const table = $57CFB523;
const a = $820103F0;
const thead = $2D298F5C;
const tbody = $BB316BB0;
const br = $2CF50F7A;
const td = $A664EDFC;
const tr = $B93B93AD;
const th = $1483CA3C;
const basefont = $C997A27A;
const p = $B7656EB4;
//invisible
const area = $B61A9737;
const base = $36BAA821;
const datalist = $41BB801A;
const head = $FB1A74A6;
const link = $21E329D3;
const meta = $53F6A414;
const noembed = $35DC71D8;
const noframes = $8EF9275D;
const param = $EA036F5E;
const rp = $065D2F8B;
const script = $75469FD3;
const source = $B04BAA1E;
const style = $244E4D3D;
const template = $08F14C20;
const track = $AB8D6A26;
const title = $FE8D4719;
end;
function lowerContains(const s: string): boolean;
begin
case lowercase(s) of
{$ifdef K3P}
'img': result := true;
'table': result := true;
'a': result := true;
{$endif}
{$ifdef K6P}
'thead': result := true;
'tbody': result := true;
'br': result := true;
{$endif}
{$ifdef K9P}
'script': result := true;
'source': result := true;
'meta': result := true;
{$endif}
{$ifdef K12P}
'basefont': result := true;
'p': result := true;
'area': result := true;
{$endif}
{$ifdef K15P}
'tr': result := true;
'td': result := true;
'th': result := true;
{$endif}
else result := false;
end;
end;
function caseHashContains(const hash: longword; const s: string): boolean;
begin
case hash of
{$ifdef K3P}
HTMLNodeNameHashs.img: result := striEqual(s, 'img');
HTMLNodeNameHashs.table: result := striEqual(s, 'table');
HTMLNodeNameHashs.a: result := striEqual(s, 'a');
{$endif}
{$ifdef K6P}
HTMLNodeNameHashs.thead: result := striEqual(s, 'thead');
HTMLNodeNameHashs.tbody: result := striEqual(s, 'tbody');
HTMLNodeNameHashs.br: result := striEqual(s, 'br');
{$endif}
{$ifdef K9P}
HTMLNodeNameHashs.script: result := striEqual(s, 'script');
HTMLNodeNameHashs.source: result := striEqual(s, 'source');
HTMLNodeNameHashs.meta: result := striEqual(s, 'meta');
{$endif}
{$ifdef K12P}
HTMLNodeNameHashs.basefont: result := striEqual(s, 'basefont');
HTMLNodeNameHashs.p: result := striEqual(s, 'p');
HTMLNodeNameHashs.area: result := striEqual(s, 'area');
{$endif}
{$ifdef K15P}
HTMLNodeNameHashs.tr: result := striEqual(s, 'tr');
HTMLNodeNameHashs.td: result := striEqual(s, 'td');
HTMLNodeNameHashs.th: result := striEqual(s, 'th');
{$endif}
else result := false;
end;
end;
function caseFirstLetter(const s: string): boolean;
begin
if length(s) = 0 then exit(false);
case s[1] of
{$if defined(K3P)}
'i', 'I': result := striEqual(s, 'img');
't', 'T': result := striEqual(s, 'table')
{$ifdef K6P}or striEqual(s, 'thead') or striEqual(s, 'tbody') {$endif}
{$ifdef K15P}or striEqual(s, 'tr') or striEqual(s, 'td') or striEqual(s, 'th') {$endif}
;
'a', 'A': result := striEqual(s, 'a') {$ifdef K12P}or striEqual(s, 'area'){$endif};
{$endif}
{$if defined(K6P)}
'b', 'B': result := striEqual(s, 'br') {$ifdef K12P}or striEqual(s, 'basefont'){$endif};
{$endif}
{$if defined(K9P)}
's', 'S': result := striEqual(s, 'script') or striEqual(s, 'source');
'm', 'M': result := striEqual(s, 'meta');
{$endif}
{$if defined(K12P)}
'p', 'P': result := striEqual(s, 'p');
{$endif}
else result := false;
end;
end;
var kinds: array[0..20] of string = ('img', 'table', 'a',
'thead', 'tbody', 'br',
'script', 'source', 'meta',
'basefont', 'p', 'area',
'tr', 'td', 'th',
'base', 'datalist', 'head', 'link', 'noembed', 'noframes');
var test: array of record
hash: longword;
s: string;
end;
hashset: TXQHashsetStrCaseInsensitiveASCII;
i, count: Integer;
begin
writeln(n);
writeln(k);
logging := true;
setlength(test, n);
for i := 0 to high(test) do begin
test[i].s := kinds[Random(k + nomatchfiller)];
if random(10) < 5 then test[i].s := uppercase(test[i].s);
test[i].hash := nodeNameHash(test[i].s);
end;
hashset.init;
for i := 0 to k - 1 do begin
hashset.include(kinds[i]);
end;
writeln;writeln('case hash');
startTiming();
count := 0;
for i := 0 to high(test) do
if caseHashContains(nodeNameHash(test[i].s), test[i].s) then inc(count);
stopTiming();
writeln(count);
writeln;writeln('case hash (cached)');
startTiming();
count := 0;
for i := 0 to high(test) do
if caseHashContains(test[i].hash, test[i].s) then inc(count);
stopTiming();
writeln(count);
writeln;writeln('hashset');
startTiming();
count := 0;
for i := 0 to high(test) do
if hashset.contains(test[i].s) then inc(count);
stopTiming();
writeln(count);
writeln;writeln('hashset (cached)');
startTiming();
count := 0;
for i := 0 to high(test) do
if hashset.findEntityWithHash(pointer(test[i].s), length(test[i].s), test[i].hash) <> nil then inc(count);
stopTiming();
writeln(count);
writeln;writeln('case letter');
startTiming();
count := 0;
for i := 0 to high(test) do
if caseFirstLetter(test[i].s) then inc(count);
stopTiming();
writeln(count);
writeln;writeln('case lowercase');
startTiming();
count := 0;
for i := 0 to high(test) do
if lowerContains(test[i].s) then inc(count);
stopTiming();
writeln(count);
end.
=========================================O1=================================
10000000
3
case hash
2020-03-28:22:05:55:266 (1): started timing of global
2020-03-28:22:05:55:851 (1): stopped timing of global run-time: 585 ms
3749857
case hash (cached)
2020-03-28:22:05:55:851 (1): started timing of global
2020-03-28:22:05:56:044 (1): stopped timing of global run-time: 193 ms
3749857
hashset
2020-03-28:22:05:56:044 (1): started timing of global
2020-03-28:22:05:56:972 (1): stopped timing of global run-time: 928 ms
3749857
hashset (cached)
2020-03-28:22:05:56:972 (1): started timing of global
2020-03-28:22:05:57:385 (1): stopped timing of global run-time: 413 ms
3749857
case letter
2020-03-28:22:05:57:385 (1): started timing of global
2020-03-28:22:05:57:601 (1): stopped timing of global run-time: 216 ms
3749857
case lowercase
2020-03-28:22:05:57:601 (1): started timing of global
2020-03-28:22:05:58:475 (1): stopped timing of global run-time: 874 ms
3749857
--------------------------------------------------------------------
10000000
9
case hash
2020-03-28:22:06:21:523 (1): started timing of global
2020-03-28:22:06:22:131 (1): stopped timing of global run-time: 608 ms
6426313
case hash (cached)
2020-03-28:22:06:22:131 (1): started timing of global
2020-03-28:22:06:22:367 (1): stopped timing of global run-time: 236 ms
6426313
hashset
2020-03-28:22:06:22:367 (1): started timing of global
2020-03-28:22:06:23:230 (1): stopped timing of global run-time: 862 ms
6426313
hashset (cached)
2020-03-28:22:06:23:230 (1): started timing of global
2020-03-28:22:06:23:686 (1): stopped timing of global run-time: 457 ms
6426313
case letter
2020-03-28:22:06:23:686 (1): started timing of global
2020-03-28:22:06:24:022 (1): stopped timing of global run-time: 336 ms
6426313
case lowercase
2020-03-28:22:06:24:022 (1): started timing of global
2020-03-28:22:06:25:299 (1): stopped timing of global run-time: 1276 ms
6426313
--------------------------------------------------------------------------
10000000
15
case hash
2020-03-28:22:06:55:562 (1): started timing of global
2020-03-28:22:06:56:207 (1): stopped timing of global run-time: 644 ms
7499955
case hash (cached)
2020-03-28:22:06:56:207 (1): started timing of global
2020-03-28:22:06:56:488 (1): stopped timing of global run-time: 281 ms
7499955
hashset
2020-03-28:22:06:56:488 (1): started timing of global
2020-03-28:22:06:57:431 (1): stopped timing of global run-time: 943 ms
7499955
hashset (cached)
2020-03-28:22:06:57:431 (1): started timing of global
2020-03-28:22:06:57:997 (1): stopped timing of global run-time: 567 ms
7499955
case letter
2020-03-28:22:06:57:997 (1): started timing of global
2020-03-28:22:06:58:424 (1): stopped timing of global run-time: 427 ms
7499955
case lowercase
2020-03-28:22:06:58:424 (1): started timing of global
2020-03-28:22:06:59:978 (1): stopped timing of global run-time: 1553 ms
7499955
=========================================O2=================================
10000000
3
case hash
2020-03-28:22:08:10:222 (1): started timing of global
2020-03-28:22:08:10:519 (1): stopped timing of global run-time: 296 ms
3749857
case hash (cached)
2020-03-28:22:08:10:519 (1): started timing of global
2020-03-28:22:08:10:685 (1): stopped timing of global run-time: 166 ms
3749857
hashset
2020-03-28:22:08:10:685 (1): started timing of global
2020-03-28:22:08:11:120 (1): stopped timing of global run-time: 435 ms
3749857
hashset (cached)
2020-03-28:22:08:11:120 (1): started timing of global
2020-03-28:22:08:11:433 (1): stopped timing of global run-time: 313 ms
3749857
case letter
2020-03-28:22:08:11:433 (1): started timing of global
2020-03-28:22:08:11:640 (1): stopped timing of global run-time: 207 ms
3749857
case lowercase
2020-03-28:22:08:11:640 (1): started timing of global
2020-03-28:22:08:12:539 (1): stopped timing of global run-time: 899 ms
3749857
-------------------------------------------------------------------------
10000000
9
case hash
2020-03-28:22:08:40:747 (1): started timing of global
2020-03-28:22:08:41:200 (1): stopped timing of global run-time: 453 ms
6426313
case hash (cached)
2020-03-28:22:08:41:200 (1): started timing of global
2020-03-28:22:08:41:454 (1): stopped timing of global run-time: 254 ms
6426313
hashset
2020-03-28:22:08:41:454 (1): started timing of global
2020-03-28:22:08:41:964 (1): stopped timing of global run-time: 511 ms
6426313
hashset (cached)
2020-03-28:22:08:41:964 (1): started timing of global
2020-03-28:22:08:42:347 (1): stopped timing of global run-time: 382 ms
6426313
case letter
2020-03-28:22:08:42:347 (1): started timing of global
2020-03-28:22:08:42:680 (1): stopped timing of global run-time: 334 ms
6426313
case lowercase
2020-03-28:22:08:42:680 (1): started timing of global
2020-03-28:22:08:44:027 (1): stopped timing of global run-time: 1346 ms
6426313
-----------------------------------------------------------------------
10000000
15
case hash
2020-03-28:22:09:06:896 (1): started timing of global
2020-03-28:22:09:07:311 (1): stopped timing of global run-time: 416 ms
7499955
case hash (cached)
2020-03-28:22:09:07:312 (1): started timing of global
2020-03-28:22:09:07:581 (1): stopped timing of global run-time: 269 ms
7499955
hashset
2020-03-28:22:09:07:581 (1): started timing of global
2020-03-28:22:09:08:113 (1): stopped timing of global run-time: 533 ms
7499955
hashset (cached)
2020-03-28:22:09:08:113 (1): started timing of global
2020-03-28:22:09:08:509 (1): stopped timing of global run-time: 395 ms
7499955
case letter
2020-03-28:22:09:08:509 (1): started timing of global
2020-03-28:22:09:08:889 (1): stopped timing of global run-time: 380 ms
7499955
case lowercase
2020-03-28:22:09:08:889 (1): started timing of global
2020-03-28:22:09:10:530 (1): stopped timing of global run-time: 1642 ms
7499955
=========================================O3=================================
10000000
3
case hash
2020-03-28:22:10:24:670 (1): started timing of global
2020-03-28:22:10:24:972 (1): stopped timing of global run-time: 303 ms
3749857
case hash (cached)
2020-03-28:22:10:24:972 (1): started timing of global
2020-03-28:22:10:25:197 (1): stopped timing of global run-time: 224 ms
3749857
hashset
2020-03-28:22:10:25:197 (1): started timing of global
2020-03-28:22:10:25:644 (1): stopped timing of global run-time: 447 ms
3749857
hashset (cached)
2020-03-28:22:10:25:644 (1): started timing of global
2020-03-28:22:10:25:952 (1): stopped timing of global run-time: 309 ms
3749857
case letter
2020-03-28:22:10:25:952 (1): started timing of global
2020-03-28:22:10:26:162 (1): stopped timing of global run-time: 210 ms
3749857
case lowercase
2020-03-28:22:10:26:162 (1): started timing of global
2020-03-28:22:10:27:080 (1): stopped timing of global run-time: 917 ms
3749857
---------------------------------------------------------------
10000000
9
case hash
2020-03-28:22:10:04:294 (1): started timing of global
2020-03-28:22:10:04:646 (1): stopped timing of global run-time: 351 ms
6426313
case hash (cached)
2020-03-28:22:10:04:646 (1): started timing of global
2020-03-28:22:10:04:859 (1): stopped timing of global run-time: 214 ms
6426313
hashset
2020-03-28:22:10:04:859 (1): started timing of global
2020-03-28:22:10:05:367 (1): stopped timing of global run-time: 508 ms
6426313
hashset (cached)
2020-03-28:22:10:05:367 (1): started timing of global
2020-03-28:22:10:05:745 (1): stopped timing of global run-time: 377 ms
6426313
case letter
2020-03-28:22:10:05:745 (1): started timing of global
2020-03-28:22:10:06:075 (1): stopped timing of global run-time: 331 ms
6426313
case lowercase
2020-03-28:22:10:06:075 (1): started timing of global
2020-03-28:22:10:07:355 (1): stopped timing of global run-time: 1279 ms
6426313
--------------------------------------------------------------------------
10000000
15
case hash
2020-03-28:22:09:29:971 (1): started timing of global
2020-03-28:22:09:30:347 (1): stopped timing of global run-time: 376 ms
7499955
case hash (cached)
2020-03-28:22:09:30:347 (1): started timing of global
2020-03-28:22:09:30:611 (1): stopped timing of global run-time: 265 ms
7499955
hashset
2020-03-28:22:09:30:612 (1): started timing of global
2020-03-28:22:09:31:139 (1): stopped timing of global run-time: 527 ms
7499955
hashset (cached)
2020-03-28:22:09:31:140 (1): started timing of global
2020-03-28:22:09:31:534 (1): stopped timing of global run-time: 394 ms
7499955
case letter
2020-03-28:22:09:31:534 (1): started timing of global
2020-03-28:22:09:31:896 (1): stopped timing of global run-time: 363 ms
7499955
case lowercase
2020-03-28:22:09:31:896 (1): started timing of global
2020-03-28:22:09:33:589 (1): stopped timing of global run-time: 1692 ms
7499955
=========================================O4=================================
10000000
3
case hash
2020-03-28:22:10:47:365 (1): started timing of global
2020-03-28:22:10:47:661 (1): stopped timing of global run-time: 295 ms
3749857
case hash (cached)
2020-03-28:22:10:47:661 (1): started timing of global
2020-03-28:22:10:47:830 (1): stopped timing of global run-time: 170 ms
3749857
hashset
2020-03-28:22:10:47:830 (1): started timing of global
2020-03-28:22:10:48:272 (1): stopped timing of global run-time: 442 ms
3749857
hashset (cached)
2020-03-28:22:10:48:272 (1): started timing of global
2020-03-28:22:10:48:595 (1): stopped timing of global run-time: 323 ms
3749857
case letter
2020-03-28:22:10:48:595 (1): started timing of global
2020-03-28:22:10:48:801 (1): stopped timing of global run-time: 205 ms
3749857
case lowercase
2020-03-28:22:10:48:801 (1): started timing of global
2020-03-28:22:10:49:729 (1): stopped timing of global run-time: 928 ms
3749857
-------------------------------------------------------------------
10000000
9
case hash
2020-03-28:22:11:08:496 (1): started timing of global
2020-03-28:22:11:08:853 (1): stopped timing of global run-time: 357 ms
6426313
case hash (cached)
2020-03-28:22:11:08:853 (1): started timing of global
2020-03-28:22:11:09:066 (1): stopped timing of global run-time: 214 ms
6426313
hashset
2020-03-28:22:11:09:066 (1): started timing of global
2020-03-28:22:11:09:564 (1): stopped timing of global run-time: 498 ms
6426313
hashset (cached)
2020-03-28:22:11:09:564 (1): started timing of global
2020-03-28:22:11:09:946 (1): stopped timing of global run-time: 382 ms
6426313
case letter
2020-03-28:22:11:09:946 (1): started timing of global
2020-03-28:22:11:10:287 (1): stopped timing of global run-time: 340 ms
6426313
case lowercase
2020-03-28:22:11:10:287 (1): started timing of global
2020-03-28:22:11:11:572 (1): stopped timing of global run-time: 1286 ms
6426313
-----------------------------------------------------------------------
10000000
15
case hash
2020-03-28:22:11:28:465 (1): started timing of global
2020-03-28:22:11:28:843 (1): stopped timing of global run-time: 379 ms
7499955
case hash (cached)
2020-03-28:22:11:28:843 (1): started timing of global
2020-03-28:22:11:29:107 (1): stopped timing of global run-time: 263 ms
7499955
hashset
2020-03-28:22:11:29:107 (1): started timing of global
2020-03-28:22:11:29:633 (1): stopped timing of global run-time: 526 ms
7499955
hashset (cached)
2020-03-28:22:11:29:633 (1): started timing of global
2020-03-28:22:11:30:026 (1): stopped timing of global run-time: 394 ms
7499955
case letter
2020-03-28:22:11:30:026 (1): started timing of global
2020-03-28:22:11:30:386 (1): stopped timing of global run-time: 359 ms
7499955
case lowercase
2020-03-28:22:11:30:386 (1): started timing of global
2020-03-28:22:11:31:953 (1): stopped timing of global run-time: 1568 ms
7499955
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment