map
title: Map Benchmark tags:
Benchmark
Map
categories:
Data Structure
摘要
对如下map实现作benchmark：
standard map
standard hash map
google dense hash map
google sparse hash map
nark hash map
概念
google dense & sparse hash map
不同点
dense hash map
查找速度快 ^[1]^
使用之前，必须调用
set_empty_key()函数设置empty bucket的key值 ^[1]^
sparse hash map
空间开销小，每个entry占用1-2bit ^[1]^
相同点
如果需要删除操作，必须调用
set_deleted_key()函数设置deleted bucket的key值 ^[1]^在初始化时，插入元素的数量可以作为可选参数，相比于SGI的
hash_map可以把桶的数量作为初始化时的可选参数 ^[1]^erase()操作 ^[1]^erase()操作不会立即释放内存，也不会导致哈希表的resize操作；相反，调用erase()会增加哈希表的内存占用 ^[2,3]^erase()操作不会使迭代器失效，也就是说，下面代码合法for (it = ht.begin(); it != ht.end(); ++it) if (...) ht.erase(it);erase()操作不会减少哈希表的内存占用，其会在下次调用insert()函数时compact，但是可以通过调用resize()方法手动compactresize(0)可以调整哈希表的size为最小的合法值 ^[2,3]^
sparse_hash_map::iterator和sparse_hash_map::iterator不是一个可变迭代器，因为sparse_hash_map::value_type和dense_hash_map::value_type不能被赋值 ^[2,3]^sparse_hash_map和dense_hash_map必须是plain old data^[4,2,3]^
适用
dense hash map
适用于需要快速访问存储在内存中的相对较小的“字典”的应用程序 ^[2]^
sparse hash map
适用于需要在内存中存储大型“字典”的应用程序，以及需要这些字典持久化的应用程序 ^[3]^
底层数据结构
基于二次探测的 hash table ^[1]^
nark hash map
特点
使用两块连续内存 ^[5]^
缓存hash value (hash key) ^[5]^
删除元素更简单 ^[5]^
直接将末尾元素拷贝到删除元素处
删除元素时插入空闲链表，优先从空闲链表分配（id 不变）
底层数据结构
基于开链的hash table ^[6]^
测试
环境
$ uname -a
Linux c3-data-ml00.bj 3.10.0-514.16.1.el7.x86_64 #1 SMP Wed Apr 12 15:04:24 UTC 2017 x86_64 x86_64 x86_64 GNU/Linux
$ lscpu
Architecture: x86_64
CPU op-mode(s): 32-bit, 64-bit
...
Model name: Intel(R) Xeon(R) CPU E5-2640 v2 @ 2.00GHz
CPU MHz: 2303.515
...
$ gcc -v
...
Thread model: posix
gcc version 4.8.5 20150623 (Red Hat 4.8.5-11) (GCC)说明
实验在google item_hash_map.cc ^[7]^ 基础上进行修改，添加支持nark hash map(gold_hash_map)，针对Hash Map的不同实现、Key的不同大小，指定迭代次数执行map的相关操作并进行耗时统计，对统计结果进行对比。
不同的Hash Map实现说明如下表所示。
名称
说明
sparse_hash_map
google sparse hash map
dense_hash_map
google dense hash map
unordered_map
standard hash_map
map
standard map
gold_hash_map
nark hash map
不同操作说明如下表所示。
操作
说明
map_grow
插入指定迭代次数元素
map_predict/grow
hash map初始化时指定元素数量为指定迭代次数，然后插入指定迭代次数元素
map_replace
替换指定迭代次数元素值
map_fetch_random
随机遍历hash map（元素数量为指定的迭代次数）
map_fetch_sequential
顺序遍历hash map（元素数量为指定的迭代次数）
map_fetch_empty
判断元素是否在map内（元素数量和循环次数为指定的迭代次数）
map_remove
删除所有元素（初始数量为指定的迭代次数）
map_toggle
添加一个元素，紧接着删除该元素（次数指定的迭代次数）
map_iterate
使用迭代器遍历map
迭代次数如下表所示。
Key大小(byte)
迭代次数
4
10000000
8
5000000
16
2500000
256
312500
实验共进行8组，结果参见链接 ^[8]^，示例结果参考附录，统计对应变量去除最大、最小值后的平均值，统计程序 ^[9]^ 见附录。
编译
编译命令如下。
$ g++ -DHAVE_CONFIG_H -I. -I./src -I./src -std=c++11 -D_GNU_SOURCE -I../nark-bone/src -I../nark-hashmap/src -Wall -W -Wwrite-strings -Woverloaded-virtual -Wshadow -g -O2 -MT time_hash_map-time_hash_map.o -MD -MP -MF .deps/time_hash_map-time_hash_map.Tpo -c -o time_hash_map-time_hash_map.o `test -f 'src/time_hash_map.cc' || echo './'`src/time_hash_map.cc结果
测试结果说明
key为4byte, map_grow操作，不同hash map实现的耗时对比。
++++++++++++++++++++4 byte && map_grow++++++++++++++++++++
'SPARSE_HASH_MAP' : 175.0
'DENSE_HASH_MAP' : 37.6
'STANDARD HASH_MAP' : 78.9
'STANDARD MAP' : 457.2
'NARK MAP' : 43.8测试结果
random fetch(find)
++++++++++++++++++++4 byte && map_fetch_random++++++++++++++++++++
'SPARSE_HASH_MAP': 145.0
'DENSE_HASH_MAP': 20.8
'STANDARD HASH_MAP': 72.5
'STANDARD MAP': 1431.9
'NARK MAP': 53.1
++++++++++++++++++++8 byte && map_fetch_random++++++++++++++++++++
'SPARSE_HASH_MAP': 141.4
'DENSE_HASH_MAP': 29.7
'STANDARD HASH_MAP': 74.0
'STANDARD MAP': 1414.0
'NARK MAP': 60.5
++++++++++++++++++++16 byte && map_fetch_random++++++++++++++++++++
'SPARSE_HASH_MAP': 147.5
'DENSE_HASH_MAP': 47.4
'STANDARD HASH_MAP': 100.9
'STANDARD MAP': 1207.7
'NARK MAP': 81.6
++++++++++++++++++++256 byte && map_fetch_random++++++++++++++++++++
'SPARSE_HASH_MAP': 183.7
'DENSE_HASH_MAP': 118.0
'STANDARD HASH_MAP': 169.5
'STANDARD MAP': 650.8
'NARK MAP': 149.7map_remove(erase)
++++++++++++++++++++4 byte && map_remove++++++++++++++++++++
'SPARSE_HASH_MAP': 49.9
'DENSE_HASH_MAP': 9.8
'STANDARD HASH_MAP': 36.2
'STANDARD MAP': 231.8
'NARK MAP': 23.7
++++++++++++++++++++8 byte && map_remove++++++++++++++++++++
'SPARSE_HASH_MAP': 54.3
'DENSE_HASH_MAP': 11.3
'STANDARD HASH_MAP': 37.8
'STANDARD MAP': 227.4
'NARK MAP': 26.3
++++++++++++++++++++16 byte && map_remove++++++++++++++++++++
'SPARSE_HASH_MAP': 64.9
'DENSE_HASH_MAP': 27.3
'STANDARD HASH_MAP': 44.1
'STANDARD MAP': 212.1
'NARK MAP': 34.6
++++++++++++++++++++256 byte && map_remove++++++++++++++++++++
'SPARSE_HASH_MAP': 305.1
'DENSE_HASH_MAP': 239.2
'STANDARD HASH_MAP': 97.3
'STANDARD MAP': 182.3
'NARK MAP': 110.7fetch empty
++++++++++++++++++++4 byte && map_fetch_empty++++++++++++++++++++
'SPARSE_HASH_MAP': 16.3
'DENSE_HASH_MAP': 4.2
'STANDARD HASH_MAP': 15.2
'STANDARD MAP': 3.9
'NARK MAP': 13.4
++++++++++++++++++++8 byte && map_fetch_empty++++++++++++++++++++
'SPARSE_HASH_MAP': 16.8
'DENSE_HASH_MAP': 6.4
'STANDARD HASH_MAP': 16.4
'STANDARD MAP': 4.3
'NARK MAP': 15.0
++++++++++++++++++++16 byte && map_fetch_empty++++++++++++++++++++
'SPARSE_HASH_MAP': 17.4
'DENSE_HASH_MAP': 7.2
'STANDARD HASH_MAP': 22.4
'STANDARD MAP': 4.3
'NARK MAP': 20.8
++++++++++++++++++++256 byte && map_fetch_empty++++++++++++++++++++
'SPARSE_HASH_MAP': 39.5
'DENSE_HASH_MAP': 29.1
'STANDARD HASH_MAP': 66.0
'STANDARD MAP': 25.1
'NARK MAP': 55.1map_fetch_sequential
++++++++++++++++++++4 byte && map_fetch_sequential++++++++++++++++++++
'SPARSE_HASH_MAP': 41.2
'DENSE_HASH_MAP': 5.0
'STANDARD HASH_MAP': 15.6
'STANDARD MAP': 269.1
'NARK MAP': 15.2
++++++++++++++++++++8 byte && map_fetch_sequential++++++++++++++++++++
'SPARSE_HASH_MAP': 44.7
'DENSE_HASH_MAP': 7.6
'STANDARD HASH_MAP': 18.7
'STANDARD MAP': 266.7
'NARK MAP': 17.3
++++++++++++++++++++16 byte && map_fetch_sequential++++++++++++++++++++
'SPARSE_HASH_MAP': 55.0
'DENSE_HASH_MAP': 19.2
'STANDARD HASH_MAP': 24.8
'STANDARD MAP': 245.5
'NARK MAP': 23.0
++++++++++++++++++++256 byte && map_fetch_sequential++++++++++++++++++++
'SPARSE_HASH_MAP': 163.4
'DENSE_HASH_MAP': 120.7
'STANDARD HASH_MAP': 124.6
'STANDARD MAP': 220.9
'NARK MAP': 69.7map_grow
++++++++++++++++++++4 byte && map_grow++++++++++++++++++++
'SPARSE_HASH_MAP': 175.0
'DENSE_HASH_MAP': 37.6
'STANDARD HASH_MAP': 78.9
'STANDARD MAP': 457.2
'NARK MAP': 43.8
++++++++++++++++++++8 byte && map_grow++++++++++++++++++++
'SPARSE_HASH_MAP': 225.0
'DENSE_HASH_MAP': 57.2
'STANDARD HASH_MAP': 81.7
'STANDARD MAP': 470.8
'NARK MAP': 62.1
++++++++++++++++++++16 byte && map_grow++++++++++++++++++++
'SPARSE_HASH_MAP': 320.1
'DENSE_HASH_MAP': 103.3
'STANDARD HASH_MAP': 105.9
'STANDARD MAP': 400.5
'NARK MAP': 78.6
++++++++++++++++++++256 byte && map_grow++++++++++++++++++++
'SPARSE_HASH_MAP': 1319.9
'DENSE_HASH_MAP': 598.2
'STANDARD HASH_MAP': 260.9
'STANDARD MAP': 298.9
'NARK MAP': 245.9map_iterate
++++++++++++++++++++4 byte && map_iterate++++++++++++++++++++
'SPARSE_HASH_MAP': 6.9
'DENSE_HASH_MAP': 5.2
'STANDARD HASH_MAP': 3.8
'STANDARD MAP': 23.0
'NARK MAP': 1.7
++++++++++++++++++++8 byte && map_iterate++++++++++++++++++++
'SPARSE_HASH_MAP': 6.5
'DENSE_HASH_MAP': 5.5
'STANDARD HASH_MAP': 3.9
'STANDARD MAP': 29.2
'NARK MAP': 2.3
++++++++++++++++++++16 byte && map_iterate++++++++++++++++++++
'SPARSE_HASH_MAP': 6.6
'DENSE_HASH_MAP': 6.8
'STANDARD HASH_MAP': 6.5
'STANDARD MAP': 18.3
'NARK MAP': 2.4
++++++++++++++++++++256 byte && map_iterate++++++++++++++++++++
'SPARSE_HASH_MAP': 21.6
'DENSE_HASH_MAP': 36.7
'STANDARD HASH_MAP': 13.3
'STANDARD MAP': 60.5
'NARK MAP': 11.4map_predict/grow
++++++++++++++++++++4 byte && map_predict/grow++++++++++++++++++++
'SPARSE_HASH_MAP': 71.2
'DENSE_HASH_MAP': 16.2
'STANDARD HASH_MAP': 50.3
'STANDARD MAP': 450.0
'NARK MAP': 37.8
++++++++++++++++++++8 byte && map_predict/grow++++++++++++++++++++
'SPARSE_HASH_MAP': 117.9
'DENSE_HASH_MAP': 18.1
'STANDARD HASH_MAP': 51.2
'STANDARD MAP': 475.4
'NARK MAP': 48.4
++++++++++++++++++++16 byte && map_predict/grow++++++++++++++++++++
'SPARSE_HASH_MAP': 181.9
'DENSE_HASH_MAP': 31.3
'STANDARD HASH_MAP': 63.1
'STANDARD MAP': 364.3
'NARK MAP': 65.1
++++++++++++++++++++256 byte && map_predict/grow++++++++++++++++++++
'SPARSE_HASH_MAP': 936.3
'DENSE_HASH_MAP': 282.0
'STANDARD HASH_MAP': 165.5
'STANDARD MAP': 301.6
'NARK MAP': 236.2map_replace
++++++++++++++++++++4 byte && map_replace++++++++++++++++++++
'SPARSE_HASH_MAP': 28.4
'DENSE_HASH_MAP': 8.5
'STANDARD HASH_MAP': 16.2
'STANDARD MAP': 254.3
'NARK MAP': 16.8
++++++++++++++++++++8 byte && map_replace++++++++++++++++++++
'SPARSE_HASH_MAP': 31.7
'DENSE_HASH_MAP': 8.3
'STANDARD HASH_MAP': 15.9
'STANDARD MAP': 276.5
'NARK MAP': 20.1
++++++++++++++++++++16 byte && map_replace++++++++++++++++++++
'SPARSE_HASH_MAP': 40.9
'DENSE_HASH_MAP': 21.3
'STANDARD HASH_MAP': 22.3
'STANDARD MAP': 211.3
'NARK MAP': 30.9
++++++++++++++++++++256 byte && map_replace++++++++++++++++++++
'SPARSE_HASH_MAP': 169.7
'DENSE_HASH_MAP': 137.5
'STANDARD HASH_MAP': 90.3
'STANDARD MAP': 221.8
'NARK MAP': 90.1map_toggle
++++++++++++++++++++4 byte && map_toggle++++++++++++++++++++
'SPARSE_HASH_MAP': 164.0
'DENSE_HASH_MAP': 46.8
'STANDARD HASH_MAP': 75.8
'STANDARD MAP': 79.8
'NARK MAP': 35.6
++++++++++++++++++++8 byte && map_toggle++++++++++++++++++++
'SPARSE_HASH_MAP': 178.8
'DENSE_HASH_MAP': 51.4
'STANDARD HASH_MAP': 79.1
'STANDARD MAP': 78.0
'NARK MAP': 43.8
++++++++++++++++++++16 byte && map_toggle++++++++++++++++++++
'SPARSE_HASH_MAP': 197.1
'DENSE_HASH_MAP': 74.7
'STANDARD HASH_MAP': 95.8
'STANDARD MAP': 77.9
'NARK MAP': 67.0
++++++++++++++++++++256 byte && map_toggle++++++++++++++++++++
'SPARSE_HASH_MAP': 529.6
'DENSE_HASH_MAP': 284.9
'STANDARD HASH_MAP': 260.3
'STANDARD MAP': 171.5
'NARK MAP': 145.0参考
附录
耗时统计程序
#!/bin/python3
"""
@file analysis.py
@author bovenson
@date 2018-11-29 18:55:15
@desc -
"""
import os
import pathlib
import re
size_list = [4, 8, 16, 256]
map_list = ['SPARSE_HASH_MAP', 'DENSE_HASH_MAP', 'STANDARD HASH_MAP', 'STANDARD MAP', 'NARK MAP']
item_list = ['map_grow', 'map_predict/grow', 'map_replace', 'map_fetch_random', 'map_fetch_sequential',
'map_fetch_empty', 'map_remove', 'map_toggle', 'map_iterate']
res = [[[[] for _ in item_list] for _ in map_list] for _ in size_list]
def extract_data(data):
_res = re.findall(r'(\d+\.\d+) ns', data)
# print(len(_res))
_cnt = 0
for _i in range(len(size_list)):
for _j in range(len(map_list)):
for _k in range(len(item_list)):
res[_i][_j][_k].append(float(_res[_cnt]))
_cnt += 1
file_list = []
log_file_path = './log'
for item in os.listdir(log_file_path):
item = os.path.join(log_file_path, item)
if os.path.isfile(item):
with open(item) as f:
extract_data(f.read())
# print(res[0][0][0])
# print(res[-1][-1][-2])
# average
for _i in range(len(size_list)):
for _j in range(len(map_list)):
for _k in range(len(item_list)):
_cur = res[_i][_j][_k]
res[_i][_j][_k] = (sum(_cur) - min(_cur) - max(_cur)) / (len(_cur) - 2)
# print(res[0][0][0])
# print(res[-1][-1][-2])
def print_all():
with open('all.txt', 'w+') as f:
for _i in range(len(size_list)):
for _k in range(len(item_list)):
f.write('\n' + '+' * 20 + str(size_list[_i]) + ' byte ' + ' && ' + str(item_list[_k]) + '+' * 20)
for _j in range(len(map_list)):
f.write(repr(map_list[_j]).rjust(20) + ': ' + '{0:.1f}'.format(res[_i][_j][_k]))
# print oper
def print_oper(oper):
_k = item_list.index(oper)
_file_name = os.path.join('.', 'analysis', (oper + '.txt').replace('/', ''))
with open(_file_name, 'w+') as f:
for _i in range(len(size_list)):
f.write('\n' + '+' * 20 + str(size_list[_i]) + ' byte ' + ' && ' + str(item_list[_k]) + '+' * 20 + '\n')
for _j in range(len(map_list)):
f.write(repr(map_list[_j]).rjust(20) + ': ' + '{0:.1f}'.format(res[_i][_j][_k]) + '\n')
for _oper in item_list:
print_oper(_oper)time_hash_map示例输出
======
Linux | **** | 3.10.0-514.16.1.el7.x86_64 | #1 SMP Wed Apr 12 15:04:24 UTC 2017 | x86_64
Average over 10000000 iterations
Current time (GMT): Thu Nov 29 10:19:21 2018
SPARSE_HASH_MAP (4 byte objects, 10000000 iterations):
map_grow 176.2 ns (23421757 hashes, 43421814 copies)
map_predict/grow 71.6 ns (10000000 hashes, 30000000 copies)
map_replace 28.1 ns (10000000 hashes, 0 copies)
map_fetch_random 143.2 ns (10000000 hashes, 0 copies)
map_fetch_sequential 41.0 ns (10000000 hashes, 0 copies)
map_fetch_empty 16.0 ns ( 0 hashes, 0 copies)
map_remove 49.9 ns (10000000 hashes, 10000000 copies)
map_toggle 164.0 ns (20399999 hashes, 41599996 copies)
map_iterate 7.0 ns ( 0 hashes, 0 copies)
stresshashfunction map_size=256 stride=1: 280.5ns/insertion
stresshashfunction map_size=256 stride=256: 204.2ns/insertion
stresshashfunction map_size=1024 stride=1: 498.6ns/insertion
stresshashfunction map_size=1024 stride=1024: 509.8ns/insertion
DENSE_HASH_MAP (4 byte objects, 10000000 iterations):
map_grow 36.2 ns (26777220 hashes, 113886160 copies)
map_predict/grow 16.1 ns (10000000 hashes, 30000000 copies)
map_replace 8.8 ns (10000000 hashes, 0 copies)
map_fetch_random 21.1 ns (10000000 hashes, 0 copies)
map_fetch_sequential 5.0 ns (10000000 hashes, 0 copies)
map_fetch_empty 4.0 ns ( 0 hashes, 0 copies)
map_remove 10.1 ns (10000000 hashes, 10000000 copies)
map_toggle 47.0 ns (20624999 hashes, 64999960 copies)
map_iterate 5.3 ns ( 0 hashes, 0 copies)
stresshashfunction map_size=256 stride=1: 45.2ns/insertion
stresshashfunction map_size=256 stride=256: 23.0ns/insertion
stresshashfunction map_size=1024 stride=1: 85.3ns/insertion
stresshashfunction map_size=1024 stride=1024: 54.7ns/insertion
STANDARD HASH_MAP (4 byte objects, 10000000 iterations):
map_grow 78.4 ns (27427396 hashes, 30000000 copies)
map_predict/grow 50.4 ns (10000000 hashes, 30000000 copies)
map_replace 16.5 ns (10000000 hashes, 0 copies)
map_fetch_random 72.0 ns (10000000 hashes, 0 copies)
map_fetch_sequential 15.7 ns (10000000 hashes, 0 copies)
map_fetch_empty 15.2 ns (10000000 hashes, 0 copies)
map_remove 36.0 ns (10000000 hashes, 0 copies)
map_toggle 76.1 ns (20000000 hashes, 30000000 copies)
map_iterate 3.8 ns ( 0 hashes, 0 copies)
stresshashfunction map_size=256 stride=1: 52.3ns/insertion
stresshashfunction map_size=256 stride=256: 51.4ns/insertion
stresshashfunction map_size=1024 stride=1: 54.1ns/insertion
stresshashfunction map_size=1024 stride=1024: 55.2ns/insertion
STANDARD MAP (4 byte objects, 10000000 iterations):
map_grow 449.7 ns ( 0 hashes, 10000000 copies)
map_predict/grow 436.5 ns ( 0 hashes, 10000000 copies)
map_replace 251.7 ns ( 0 hashes, 0 copies)
map_fetch_random 1412.9 ns ( 0 hashes, 0 copies)
map_fetch_sequential 267.5 ns ( 0 hashes, 0 copies)
map_fetch_empty 3.9 ns ( 0 hashes, 0 copies)
map_remove 233.2 ns ( 0 hashes, 0 copies)
map_toggle 79.9 ns ( 0 hashes, 10000000 copies)
map_iterate 22.9 ns ( 0 hashes, 0 copies)
stresshashfunction map_size=256 stride=1: 62.2ns/insertion
stresshashfunction map_size=256 stride=256: 62.4ns/insertion
stresshashfunction map_size=1024 stride=1: 69.8ns/insertion
stresshashfunction map_size=1024 stride=1024: 69.2ns/insertion
NARK MAP (4 byte objects, 10000000 iterations):
map_grow 43.2 ns (20066444 hashes, 36777215 copies)
map_predict/grow 37.8 ns (20066444 hashes, 36777215 copies)
map_replace 16.4 ns (10000000 hashes, 10000000 copies)
map_fetch_random 52.6 ns (10000000 hashes, 0 copies)
map_fetch_sequential 14.8 ns (10000000 hashes, 0 copies)
map_fetch_empty 13.7 ns (10000000 hashes, 0 copies)
map_remove 23.9 ns (15000000 hashes, 5000000 copies)
map_toggle 35.8 ns (20000000 hashes, 20000000 copies)
map_iterate 1.8 ns ( 0 hashes, 0 copies)
stresshashfunction map_size=256 stride=1: 47.6ns/insertion
stresshashfunction map_size=256 stride=256: 47.8ns/insertion
stresshashfunction map_size=1024 stride=1: 40.3ns/insertion
stresshashfunction map_size=1024 stride=1024: 41.4ns/insertion
SPARSE_HASH_MAP (8 byte objects, 5000000 iterations):
map_grow 224.4 ns (11710870 hashes, 21710924 copies)
map_predict/grow 119.0 ns ( 5000000 hashes, 15000000 copies)
map_replace 32.2 ns ( 5000000 hashes, 0 copies)
map_fetch_random 140.8 ns ( 5000000 hashes, 0 copies)
map_fetch_sequential 45.3 ns ( 5000000 hashes, 0 copies)
map_fetch_empty 16.4 ns ( 0 hashes, 0 copies)
map_remove 53.6 ns ( 5000000 hashes, 5000000 copies)
map_toggle 178.1 ns (10199999 hashes, 20799996 copies)
map_iterate 6.3 ns ( 0 hashes, 0 copies)
stresshashfunction map_size=256 stride=1: 273.6ns/insertion
stresshashfunction map_size=256 stride=256: 200.3ns/insertion
stresshashfunction map_size=1024 stride=1: 489.5ns/insertion
stresshashfunction map_size=1024 stride=1024: 505.4ns/insertion
DENSE_HASH_MAP (8 byte objects, 5000000 iterations):
map_grow 52.8 ns (13388611 hashes, 56943112 copies)
map_predict/grow 18.0 ns ( 5000000 hashes, 15000000 copies)
map_replace 7.9 ns ( 5000000 hashes, 0 copies)
map_fetch_random 29.8 ns ( 5000000 hashes, 0 copies)
map_fetch_sequential 7.6 ns ( 5000000 hashes, 0 copies)
map_fetch_empty 6.7 ns ( 0 hashes, 0 copies)
map_remove 11.5 ns ( 5000000 hashes, 5000000 copies)
map_toggle 52.5 ns (10312499 hashes, 32499960 copies)
map_iterate 5.4 ns ( 0 hashes, 0 copies)
stresshashfunction map_size=256 stride=1: 45.2ns/insertion
stresshashfunction map_size=256 stride=256: 16.8ns/insertion
stresshashfunction map_size=1024 stride=1: 82.1ns/insertion
stresshashfunction map_size=1024 stride=1024: 52.8ns/insertion
STANDARD HASH_MAP (8 byte objects, 5000000 iterations):
map_grow 86.4 ns (13582537 hashes, 15000000 copies)
map_predict/grow 51.1 ns ( 5000000 hashes, 15000000 copies)
map_replace 15.5 ns ( 5000000 hashes, 0 copies)
map_fetch_random 73.4 ns ( 5000000 hashes, 0 copies)
map_fetch_sequential 18.8 ns ( 5000000 hashes, 0 copies)
map_fetch_empty 16.3 ns ( 5000000 hashes, 0 copies)
map_remove 38.3 ns ( 5000000 hashes, 0 copies)
map_toggle 81.0 ns (10000000 hashes, 15000000 copies)
map_iterate 4.0 ns ( 0 hashes, 0 copies)
stresshashfunction map_size=256 stride=1: 55.0ns/insertion
stresshashfunction map_size=256 stride=256: 59.0ns/insertion
stresshashfunction map_size=1024 stride=1: 60.7ns/insertion
stresshashfunction map_size=1024 stride=1024: 61.3ns/insertion
STANDARD MAP (8 byte objects, 5000000 iterations):
map_grow 474.8 ns ( 0 hashes, 5000000 copies)
map_predict/grow 466.7 ns ( 0 hashes, 5000000 copies)
map_replace 269.3 ns ( 0 hashes, 0 copies)
map_fetch_random 1419.0 ns ( 0 hashes, 0 copies)
map_fetch_sequential 277.7 ns ( 0 hashes, 0 copies)
map_fetch_empty 4.3 ns ( 0 hashes, 0 copies)
map_remove 232.6 ns ( 0 hashes, 0 copies)
map_toggle 78.2 ns ( 0 hashes, 5000000 copies)
map_iterate 28.9 ns ( 0 hashes, 0 copies)
stresshashfunction map_size=256 stride=1: 63.3ns/insertion
stresshashfunction map_size=256 stride=256: 63.3ns/insertion
stresshashfunction map_size=1024 stride=1: 76.0ns/insertion
stresshashfunction map_size=1024 stride=1024: 71.0ns/insertion
NARK MAP (8 byte objects, 5000000 iterations):
map_grow 62.1 ns ( 5000000 hashes, 18388607 copies)
map_predict/grow 48.9 ns ( 5000000 hashes, 18388607 copies)
map_replace 20.3 ns ( 5000000 hashes, 5000000 copies)
map_fetch_random 60.0 ns ( 5000000 hashes, 0 copies)
map_fetch_sequential 16.9 ns ( 5000000 hashes, 0 copies)
map_fetch_empty 14.7 ns ( 5000000 hashes, 0 copies)
map_remove 26.5 ns ( 5000000 hashes, 2500000 copies)
map_toggle 44.2 ns (10000000 hashes, 10000000 copies)
map_iterate 2.3 ns ( 0 hashes, 0 copies)
stresshashfunction map_size=256 stride=1: 48.5ns/insertion
stresshashfunction map_size=256 stride=256: 51.7ns/insertion
stresshashfunction map_size=1024 stride=1: 41.4ns/insertion
stresshashfunction map_size=1024 stride=1024: 41.7ns/insertion
SPARSE_HASH_MAP (16 byte objects, 2500000 iterations):
map_grow 320.7 ns ( 5855426 hashes, 10855477 copies)
map_predict/grow 181.2 ns ( 2500000 hashes, 7500000 copies)
map_replace 41.1 ns ( 2500000 hashes, 0 copies)
map_fetch_random 146.2 ns ( 2500000 hashes, 0 copies)
map_fetch_sequential 55.0 ns ( 2500000 hashes, 0 copies)
map_fetch_empty 17.4 ns ( 0 hashes, 0 copies)
map_remove 63.2 ns ( 2500000 hashes, 2500000 copies)
map_toggle 197.4 ns ( 5099999 hashes, 10399996 copies)
map_iterate 6.5 ns ( 0 hashes, 0 copies)
DENSE_HASH_MAP (16 byte objects, 2500000 iterations):
map_grow 102.4 ns ( 6694306 hashes, 28471584 copies)
map_predict/grow 29.9 ns ( 2500000 hashes, 7500000 copies)
map_replace 22.0 ns ( 2500000 hashes, 0 copies)
map_fetch_random 48.6 ns ( 2500000 hashes, 0 copies)
map_fetch_sequential 19.4 ns ( 2500000 hashes, 0 copies)
map_fetch_empty 7.2 ns ( 0 hashes, 0 copies)
map_remove 27.7 ns ( 2500000 hashes, 2500000 copies)
map_toggle 72.3 ns ( 5156249 hashes, 16249960 copies)
map_iterate 6.7 ns ( 0 hashes, 0 copies)
STANDARD HASH_MAP (16 byte objects, 2500000 iterations):
map_grow 106.5 ns ( 6726830 hashes, 7500000 copies)
map_predict/grow 61.6 ns ( 2500000 hashes, 7500000 copies)
map_replace 20.8 ns ( 2500000 hashes, 0 copies)
map_fetch_random 103.0 ns ( 2500000 hashes, 0 copies)
map_fetch_sequential 25.1 ns ( 2500000 hashes, 0 copies)
map_fetch_empty 22.2 ns ( 2500000 hashes, 0 copies)
map_remove 42.0 ns ( 2500000 hashes, 0 copies)
map_toggle 97.1 ns ( 5000000 hashes, 7500000 copies)
map_iterate 6.5 ns ( 0 hashes, 0 copies)
STANDARD MAP (16 byte objects, 2500000 iterations):
map_grow 395.0 ns ( 0 hashes, 2500000 copies)
map_predict/grow 359.2 ns ( 0 hashes, 2500000 copies)
map_replace 209.0 ns ( 0 hashes, 0 copies)
map_fetch_random 1195.1 ns ( 0 hashes, 0 copies)
map_fetch_sequential 246.8 ns ( 0 hashes, 0 copies)
map_fetch_empty 4.4 ns ( 0 hashes, 0 copies)
map_remove 217.2 ns ( 0 hashes, 0 copies)
map_toggle 78.6 ns ( 0 hashes, 2500000 copies)
map_iterate 17.4 ns ( 0 hashes, 0 copies)
NARK MAP (16 byte objects, 2500000 iterations):
map_grow 80.8 ns ( 2500000 hashes, 9194303 copies)
map_predict/grow 67.2 ns ( 2500000 hashes, 9194303 copies)
map_replace 29.1 ns ( 2500000 hashes, 2500000 copies)
map_fetch_random 78.3 ns ( 2500000 hashes, 0 copies)
map_fetch_sequential 23.3 ns ( 2500000 hashes, 0 copies)
map_fetch_empty 20.8 ns ( 2500000 hashes, 0 copies)
map_remove 35.4 ns ( 2500000 hashes, 1250000 copies)
map_toggle 67.8 ns ( 5000000 hashes, 5000000 copies)
map_iterate 2.4 ns ( 0 hashes, 0 copies)
SPARSE_HASH_MAP (256 byte objects, 312500 iterations):
map_grow 1325.5 ns ( 731912 hashes, 1356954 copies)
map_predict/grow 937.7 ns ( 312500 hashes, 937500 copies)
map_replace 156.6 ns ( 312500 hashes, 0 copies)
map_fetch_random 186.5 ns ( 312500 hashes, 0 copies)
map_fetch_sequential 163.5 ns ( 312500 hashes, 0 copies)
map_fetch_empty 40.6 ns ( 0 hashes, 0 copies)
map_remove 318.2 ns ( 312500 hashes, 312500 copies)
map_toggle 516.6 ns ( 637499 hashes, 1299996 copies)
map_iterate 21.1 ns ( 0 hashes, 0 copies)
DENSE_HASH_MAP (256 byte objects, 312500 iterations):
map_grow 605.8 ns ( 836787 hashes, 3558980 copies)
map_predict/grow 262.4 ns ( 312500 hashes, 937500 copies)
map_replace 136.2 ns ( 312500 hashes, 0 copies)
map_fetch_random 117.5 ns ( 312500 hashes, 0 copies)
map_fetch_sequential 121.2 ns ( 312500 hashes, 0 copies)
map_fetch_empty 30.0 ns ( 0 hashes, 0 copies)
map_remove 228.0 ns ( 312500 hashes, 312500 copies)
map_toggle 289.7 ns ( 644531 hashes, 2031240 copies)
map_iterate 35.7 ns ( 0 hashes, 0 copies)
STANDARD HASH_MAP (256 byte objects, 312500 iterations):
map_grow 273.9 ns ( 817789 hashes, 937500 copies)
map_predict/grow 153.5 ns ( 312500 hashes, 937500 copies)
map_replace 84.3 ns ( 312500 hashes, 0 copies)
map_fetch_random 171.4 ns ( 312500 hashes, 0 copies)
map_fetch_sequential 122.5 ns ( 312500 hashes, 0 copies)
map_fetch_empty 61.9 ns ( 312500 hashes, 0 copies)
map_remove 100.0 ns ( 312500 hashes, 0 copies)
map_toggle 265.7 ns ( 625000 hashes, 937500 copies)
map_iterate 13.0 ns ( 0 hashes, 0 copies)
STANDARD MAP (256 byte objects, 312500 iterations):
map_grow 255.1 ns ( 0 hashes, 312500 copies)
map_predict/grow 308.2 ns ( 0 hashes, 312500 copies)
map_replace 219.9 ns ( 0 hashes, 0 copies)
map_fetch_random 676.3 ns ( 0 hashes, 0 copies)
map_fetch_sequential 222.5 ns ( 0 hashes, 0 copies)
map_fetch_empty 25.5 ns ( 0 hashes, 0 copies)
map_remove 194.3 ns ( 0 hashes, 0 copies)
map_toggle 170.6 ns ( 0 hashes, 312500 copies)
map_iterate 60.9 ns ( 0 hashes, 0 copies)
NARK MAP (256 byte objects, 312500 iterations):
map_grow 260.3 ns ( 312500 hashes, 836787 copies)
map_predict/grow 240.7 ns ( 312500 hashes, 836787 copies)
map_replace 92.2 ns ( 312500 hashes, 0 copies)
map_fetch_random 149.5 ns ( 312500 hashes, 0 copies)
map_fetch_sequential 70.2 ns ( 312500 hashes, 0 copies)
map_fetch_empty 54.1 ns ( 312500 hashes, 0 copies)
map_remove 111.5 ns ( 312500 hashes, 156250 copies)
map_toggle 144.5 ns ( 625000 hashes, 312500 copies)
map_iterate 11.4 ns ( 0 hashes, 0 copies)最后更新于
这有帮助吗？