runaway rehash with ska::prime_number_hash_policy

[sharkzombie]

I was benchmarking hashes and there seem to be a runaway rehash with some degenerate set of keys, with process size killed when out of memory after growing past 100gigs... Which is too bad because prime number policy provides at least 50% improvement for when it does not run away.

The smallest case I can reduce it to is this, I've used same size data structures that I've used in case this makes any difference.

#include <iostream>
#include <cstdint>

#include "flat_hash_map.hpp"

struct Key {
  uint64_t x = 0;
  std::string y;

  bool operator==(const Key& other) const {
    return std::tie(x,y) == std::tie(other.x, other.y);
  }
};

struct KeyHash {
  size_t operator() (const Key& k) const {
    return 0;  // degenerate case to repro runaway memory problem
  }
  using hash_policy = ska::prime_number_hash_policy;
};

struct Foo {
    char x[16];
};

typedef ska::flat_hash_map<Key, Foo, KeyHash, std::equal_to<Key>> Map;


int main (int argc, char *argv[])
{
  Map map(10000000);
  for (size_t i = 0; i < 1024; i++) {
      map.emplace (std::make_pair(Key{i, std::string()}, Foo()));
  }
}

Obviously above is just a degenerate example, the one where I found it was using this set of keys, with identity (ie hash function returning the key value), the ordering is same order as I was trying to insert them in, when killed ./a.out was about 40g in size.

std::vector<uint64_t> keys = {
  738941615617162223, 625883680492147, 738941615655191112, 7852353832143828,
  738941615724408081, 7852354032426516, 738941615729858855, 7852354048193088,
  738941615969493070, 7852354741499990, 738941616062643868, 625884125988607,
  738941616142228016, 7852355241254612, 738941616184859040, 7852355364591056,
  738941616303320353, 625884366665147, 349874591868649478, 349874591868649479,
  738941616381784144, 7852355934330842, 738941616403210362, 7852355996321796,
  738941616487037904, 7852356238846246, 738941616627107452, 7852356644094970,
  738941616700739445, 625884764084800, 738941616722897509, 7852356921230312,
  738941616767899804, 738941616767891735, 738941616851739636, 7852357293994216,
  738941616876716233, 738941616876714484, 738941616921974211, 7852357497196458,
  738941616963545944, 738941616963542633, 738941616980982919, 625885044327925,
  738941617022752078, 625885086095578, 738941617055137918, 7852357882459820,
  738941617124348842, 738941617124344688, 738941617191580739, 7852358277213168,
  738941617223978591, 7852358370946978, 738941617379757779, 625885443103342,
  738941617578527414, 7852359396718646, 738941617666002087, 7852359649796182,
  738941617667282417, 7852359653500506, 738941617716735517, 7852359796576376,
  738941617743615770, 738941617743613126, 738941617766981741, 738941617766978324,
  738941617789814498, 738941617789811459, 738941617873007059, 7852360248695672,
  738941617881843508, 7852360274262772, 738941617951309984, 738941617951306711,
  738941617971858215, 738941617971854957, 738941617998133799, 625886061477694,
  738941618006963156, 7852360636252994, 349874591868649480, 349874591868649481,
  738941618154281475, 625886217626626, 738941618284342601, 738941618284339923,
  738941618358772775, 738941618358771130, 738941618371653781, 7852361691369358,
  738941618415674459, 7852361818729738, 738941618442746489, 738941618442742743,
  738941618481714588, 625886545060418, 738941618512455194, 738941618512452825,
  738941618591103511, 625886654446743, 738941618699309050, 738941618699306060,
  738941618746220638, 625886809565979, 349874591868649482, 349874591868649483,
  738941618796700248, 738941618796697486, 738941618799949387, 7852362930502734,
  738941618880836902, 7852363164524156, 738941618882244537, 625886945589498,
  738941618888916843, 7852363187901470, 738941618921360649, 7852363281756970,
  738941618923148749, 738941618923146029, 738941618944484040, 7852363348665792,
  738941618999438091, 7852363507657022, 738941619009972512, 625887073317417,
  738941619038562162, 625887101906993, 738941619039483590, 625887102829291,
  738941619208228001, 7852364111723714, 738941619222452986, 738941619222450344,
  738941619289766030, 738941619289763240, 738941619340879860, 625887404223569,
  349874591868649484, 349874591868649485, 738941619502234468, 625887565579252,
  738941619520703266, 7852365015769768, 738941619640551203, 738941619640548509,
  738941619675754240, 625887739099816, 738941619682186317, 7852365482967952,
  738941619701766202, 625887765110605, 349874591868649478, 349874591868649479,
  738941619760838216, 7852365710515934, 738941619818327751, 625887881672105,
  738941619907638889, 7852366135236854, 738941619948733385, 625888012078801,
  738941619997533555, 7852366395322186, 738941620047746601, 7852366540596312,
  349874591868649486, 349874591868649487, 738941620066833436, 625888130178263,
  738941620071511699, 625888134857242, 738941620130238117, 625888193583305,
  738941620222382857, 738941620222379876, 738941620228859181, 7852367064580296,
  738941620229107931, 7852367065305366, 349874591868649480, 349874591868649481,
  738941620268710903, 738941620268707814, 738941620282148760, 7852367218761844,
  738941620297544002, 7852367263300722, 738941620297964862, 7852367264521094,
  738941620343839707, 7852367397245380, 738941620348223660, 738941620348220455,
  738941620391579184, 625888454922725, 738941620402625139, 7852367567321570,
  738941620406340033, 7852367578069952, 738941620412206011, 7852367595040664,
  738941620443632501, 738941620443628866, 738941620457157825, 738941620457154705,
  349874591868649488, 349874591868649489, 738941620479433657, 625888542778876,
  738941620499021321, 7852367846212718, 738941620516543669, 738941620516541162,
  738941620542795628, 738941620542793317, 738941620552038992, 738941620552035564,
  738941620574839902, 738941620574836852, 738941620599072071, 625888662417789,
  738941620602912011, 7852368146786344, 738941620602974537, 625888666319646,
  738941620605174185, 625888668519317, 738941620617290718, 738941620617287722,
  738941620618611143, 7852368192202322, 349874591868649490, 349874591868649491,
  738941620654025087, 7852368294665304, 738941620689782463, 7852368398117962,
  349874591868649482, 349874591868649483, 738941620697826179, 7852368421388558,
  738941620718982185, 625888782327290, 738941620729880968, 7852368514128058,
  738941620760190248, 7852368601820244, 738941620762635237, 7852368608895160,
  738941620863394415, 738941620863391687, 738941620867225110, 7852368911489562,
  738941620896474488, 625888959819762, 738941620902139207, 625888965484220,
  738941620907363099, 7852369027617130, 738941620909572896, 625888972918117,
  738941620918406043, 625888981751367, 738941620924950165, 625888988295379,
  738941620994503225, 7852369279727404, 738941620999501506, 738941620999497848,
  738941621017952979, 7852369347571870, 738941621022446416, 7852369360570360,
  349874591868649484, 349874591868649485, 738941621037837027, 7852369405099004,
  738941621037895182, 625889101239812, 738941621047527609, 7852369433136788,
  349874591868649492, 349874591868649493, 738941621058705566, 625889122050733,
  738941621078821785, 7852369523672892, 738941621082220016, 7852369533507246,
  738941621111540539, 7852369618337148, 738941621154498090, 7852369742621110,
  738941621218255965, 738941621218253153, 738941621218636857, 7852369928185446,
  738941621236729346, 625889300074698, 738941621265185718, 7852370062858360,
  738941621273656578, 7852370087366696, 738941621276006272, 625889339352176,
  349874591868649494, 349874591868649495, 738941621321236910, 7852370225025884,
  738941621325623297, 7852370237715530, 738941621339955207, 625889403301021,
  738941621340104352, 738941621340101376, 738941621340130280, 625889403475668,
  738941621346604525, 625889409949819, 738941621348945392, 625889412290259,
  738941621358761645, 7852370333585518, 738941621367180527, 625889430525393,
  738941621393167623, 7852370433132630, 738941621394631407, 7852370437366996,
  738941621408572454, 625889471917308, 738941621419506131, 7852370509334076,
  738941621443244014, 625889506589090, 738941621449807521, 7852370596998410,
  738941621459760610, 7852370625798396, 738941621465947087, 738941621465944057,
  738941621520084927, 7852370800328906, 349874591868649486, 349874591868649487,
  738941621551424180, 625889614770129, 738941621564704422, 7852370929419674,
  738941621579823235, 625889643168036, 738941621585333380, 7852370989098380,
  738941621593017501, 7852371011333324, 738941621606812526, 7852371051244590,
  738941621625308757, 7852371104756628, 738941621633363148, 625889696708290,
  738941621698790870, 738941621698788100, 738941621704371577, 7852371333498602,
  738941621731424797, 625889794769731, 738941621739078343, 738941621739075555,
  738941621746623263, 625889809968941, 349874591868649496, 349874591868649497,
  738941621823424569, 7852371677938866, 738941621864845131, 7852371797775732,
  738941621918387735, 625889981732432, 349874591868649488, 349874591868649489,
  738941621947877924, 7852372038000568, 738941621948848738, 738941621948845661,
  738941621954278158, 7852372056523744, 738941621978267448, 7852372125929840,
  349874591868649498, 349874591868649499, 738941621993923797, 625890057268708,
  738941622048530302, 7852372329210638, 738941622051787354, 738941622051784706,
  738941622072495098, 7852372398545920, 738941622085350445, 738941622085347863,
  738941622097227411, 7852372470099372, 738941622102993856, 7852372486781774,
  738941622117147377, 7852372527732146, 738941622117212194, 625890180557558,
  738941622163907030, 7852372663008802, 738941622165620748, 7852372667974482,
  738941622190537409, 7852372740062102, 738941622210217709, 7852372797001542,
  738941622214169151, 738941622214166745, 738941622224027950, 7852372836952680,
  738941622230969884, 7852372857040452, 738941622270002409, 738941622270000029,
  738941622317790283, 625890381134728, 738941622336695289, 7852373162921620,
  738941622341077758, 7852373175601926, 738941622355387149, 7852373217001682,
  738941622390705322, 738941622390702922, 349874591868649500, 349874591868649501,
  738941622433415223, 7852373442749772, 738941622439999633, 738941622439996642,
  738941622443569687, 625890506914978, 738941622457100900, 7852373511275428,
  738941622461434372, 7852373523813906, 738941622501734131, 7852373640408680,
  738941622506654360, 7852373654642606, 349874591868649478, 349874591868649479,
  738941622567798884, 738941622567796127, 738941622577631974, 7852373859994496,
  738941622636156732, 7852374029316900, 738941622639918112, 7852374040198018,
  738941622711132752, 625890774478076, 738941622727875188, 625890791220389,
  738941622745659520, 738941622745657239, 738941622748873513, 738941622748870838,
  738941622765904428, 7852374404699628, 738941622782089468, 625890845434494,
  738941622788918612, 738941622788915804, 738941622791548982, 625890854894050,
  738941622818543820, 625890881888592, 738941622823380605, 625890886725741,
  738941622858505988, 625890921850991, 738941622862728077, 625890926072056,
  738941622870139448, 625890933484612, 738941622913245134, 625890976591168,
  349874591868649480, 349874591868649481, 738941622962598651, 7852374973769210,
  738941622963596109, 7852374976654828, 738941622966416811, 738941622966414297,
  738941622967877474, 7852374989042132, 738941622967951292, 7852374989254866,
  738941622980834658, 7852375026527182, 738941623000241831, 7852375082676688,
  738941623015694305, 7852375127384796, 738941623029040707, 7852375165997100,
  738941623037653401, 625891100997810, 738941623043621948, 625891106967054,
  738941623048351204, 7852375221866522, 738941623052771845, 7852375234656306,
  738941623070955635, 7852375287264268, 738941623096946048, 625891160291182,
  738941623138266115, 7852375482005162, 349874591868649482, 349874591868649483,
  738941623168834729, 7852375570445536, 738941623181296901, 625891244642096,
  738941623181690638, 7852375607639822, 738941623209826140, 625891273171390,
  349874591868649490, 349874591868649491, 738941623232420469, 625891295765796,
  738941623245716043, 625891309061123, 738941623358094075, 738941623358090357,
  738941623373207117, 7852376161730440, 738941623419262571, 7852376294975036,
  738941623448501318, 738941623448498490, 738941623454064162, 738941623454061185,
  738941623501623306, 7852376533260648, 738941623510677918, 7852376559460502,
  738941623548500962, 738941623548497609, 738941623556077552, 625891619421957,
  738941623563562397, 738941623563559467, 349874591868649502, 349874591868649503,
  738941623603191112, 625891666535967, 738941623604493002, 738941623604490555,
  738941623633824243, 7852376915737330, 738941623646825989, 7852376953357668,
  349874591868649492, 349874591868649493, 738941623672089779, 7852377026450496,
  738941623681736794, 7852377054360600, 738941623711632049, 625891774977382,
  738941623784975901, 7852377353050020, 738941623813399455, 7852377435284808,
  738941623833026643, 625891896372224, 738941623834084499, 7852377495128768,
  738941623855104163, 7852377555942452, 738941623870007363, 7852377599059290,
  738941623884826313, 7852377641933938, 738941623904112297, 738941623904109960,
  738941624008105589, 738941624008102896, 738941624023548563, 7852378043281516,
  738941624048373673, 625892111719080, 738941624054287793, 7852378132215874,
  738941624062467929, 7852378155882234, 738941624090524622, 7852378237054816,
  738941624113138579, 7852378302480268, 738941624136492738, 7852378370048296,
  349874591868649504, 349874591868649505, 738941624150498430, 625892213843403,
  738941624174131224, 7852378478943630, 738941624175760651, 7852378483657272,
  738941624176379184, 7852378485444546, 738941624191474560, 7852378529101368,
  738941624197931932, 625892261277255, 738941624211509130, 7852378587088000,
  738941624214113925, 625892277458862, 738941624215721358, 7852378599270080,
  738941624217876439, 7852378605504980, 738941624288624039, 7852378810190906,
  738941624317023022, 625892380367205, 738941624322551022, 7852378908347348,
  738941624348499006, 738941624348496110, 738941624359785678, 738941624359782121,
  738941624372060019, 625892435405290, 738941624373874417, 625892437219598,
  738941624392256438, 7852379110016564, 738941624405739850, 738941624405737452,
  738941624453397223, 7852379286907700, 738941624507562681, 738941624507559739,
  738941624557355222, 738941624557352558, 738941624565109608, 738941624565107353,
  349874591868649506, 349874591868649507, 738941624601042357, 7852379714069372,
  738941624612867536, 738941624612865525, 738941624627515379, 738941624627512299,
  738941624633103660, 7852379806829922, 738941624658027639, 738941624658013220,
  738941624741362215, 7852380120039966, 738941624762099350, 7852380180035736,
  738941624768100141, 738941624768097581, 738941624781776481, 625892845122097,
  738941624781798750, 625892845144480, 738941624793192054, 738941624793189189,
  738941624863543231, 7852380473530714, 738941624871168256, 7852380495590600,
  738941624875746951, 738941624875743762, 738941624881375949, 7852380525124672,
  738941624881442302, 625892944787774, 738941624914311622, 738941624914309630,
  738941624927958198, 738941624927955444, 738941624938820863, 625893002166638,
  738941624943829965, 738941624943827121, 738941624959082004, 7852380749941226,
  349874591868649494, 349874591868649495, 738941624990719464, 738941624990716657,
  738941625007198839, 7852380889153074, 738941625034611971, 7852380968463382,
  738941625042990017, 738941625042987551, 738941625075317010, 625893138661415,
  738941625113860449, 7852381197741670, 738941625114978093, 625893178323459,
  738941625158261499, 738941625158259081, 738941625175872469, 738941625175867341,
  738941625176038423, 625893239383658, 738941625177180585, 7852381380939144,
  738941625229412283, 738941625229409485, 738941625278775859, 625893342120779,
  738941625357587622, 738941625357584872, 738941625403621226, 738941625403619111,
  738941625463787414, 625893527131851, 738941625517638283, 7852382365940508,
  349874591868649508, 349874591868649509, 738941625547573339, 738941625547569583,
  738941625548192488, 625893611536839, 738941625566335887, 738941625566332773,
  738941625586935957, 738941625586932297, 349874591868649510, 349874591868649511,
  738941625598196111, 7852382599007218, 738941625600093002, 738941625600090700,
  738941625673579673, 7852382815933618, 738941625688382396, 7852382859933460,
  738941625710736582, 625893774081913, 738941625735235808, 738941625735233404,
  738941625736294940, 7852382998554920, 738941625740323003, 7852383010207806,
  738941625752036497, 738941625752033929, 349874591868649512, 349874591868649513,
  738941625753651535, 625893816997030, 738941625762298533, 7852383073786402,
  738941631110810993, 7852398547959850, 738941631119005047, 738941631119001401,
  738941631175158525, 738941631175155239, 738941631224834008, 738941631224831176,
  349874591868649496, 349874591868649497, 738941631268324634, 738941631268322234,
  738941631299622083, 7852399094224410, 738941631333673075, 7852399192741242,
  738941631358987065, 625899422331730, 738941631370260322, 7852399298594260,
  738941631373229973, 625899436575036, 738941631378505511, 7852399322446406,
  738941631403391441, 7852399394445958, 738941631425400422, 7852399458121102,
};