Facebook ile-iṣẹ nipa ìmọ orisun imuse ti hash tabili , iṣapeye fun lilo iranti daradara. F14 ni a lo ninu awọn amayederun Facebook bi rirọpo fun ọpọlọpọ awọn oriṣi ti awọn tabili hash ati pe o le dinku agbara iranti laisi iṣẹ ṣiṣe. F14 ṣe akiyesi ṣe ju awọn tabili hash google :: sparse_hash_map, eyiti o ti gba pe o munadoko julọ ni awọn ofin lilo iranti. Koodu ise agbese ti kọ sinu C ++ ati pe o wa ninu ile-ikawe .
F14 tọka si awọn algoridimu pẹlu eto ipinnu ijamba ti o da lori hashing ilọpo meji pẹlu 14 (ẹwọn ti awọn iho 14 ti wa ni ipamọ ninu sẹẹli tabili hash kan, ati aarin laarin awọn sẹẹli jẹ iṣiro nipa lilo iṣẹ hash iranlọwọ). Lati mu awọn iṣẹ sisẹ sẹẹli pọ si, imuse naa nlo awọn itọnisọna fekito SSE2 fun awọn ọna ṣiṣe x86_64 ati NEON fun Aarch64, eyiti o fun laaye ni afiwe ipaniyan awọn iṣẹ ṣiṣe fun yiyan awọn iho pẹlu awọn ẹwọn bọtini ati sisọ awọn bọtini laarin pq. Awọn bulọọki ti awọn iho 14 ti ni ilọsiwaju ni akoko kan, eyiti o jẹ iwọntunwọnsi ti o dara julọ laarin ṣiṣe ti lilo kaṣe ero isise ati nọmba awọn ikọlu.
Ẹya pataki ti F14 ni agbara lati yan oriṣiriṣi awọn ilana ipamọ data:
- F14NodeMap - nlo iranti ti o kere julọ fun awọn bọtini nla ati alabọde. Ṣe idaniloju pe awọn eroja ti wa ni ipamọ ni aiṣe-taara pẹlu ipe si malloc lori ifibọ kọọkan;
- F14ValueMap - pese agbara iranti iwonba fun awọn bọtini kekere. Awọn eroja ti wa ni ipamọ ninu awọn sẹẹli tikararẹ (inline). Fun awọn bọtini alabọde ati nla, ọna yii nyorisi iranti ti o ṣe akiyesi;
- F14VectorMap - ṣiṣẹ yiyara fun awọn tabili nla ati awọn bọtini idiju, ṣugbọn o lọra fun awọn bọtini ti o rọrun ati awọn tabili kekere. Awọn eroja ti wa ni aba ti sinu kan continuously kún orun ati koju nipa a 32-bit atọka;
- F14FastMap jẹ ilana apapọ. Ti bọtini ba kere ju 24 baiti, lẹhinna F14ValueMap ti yan, ati pe ti o ba jẹ diẹ sii, F14VectorMap ti yan.
orisun: opennet.ru