ફેસબુક F14 હેશ ટેબલનો અમલ ખોલે છે

ફેસબુક કંપની જાહેરાત કરી હેશ કોષ્ટકોના ઓપન સોર્સ અમલીકરણ વિશે F14, કાર્યક્ષમ મેમરી વપરાશ માટે ઑપ્ટિમાઇઝ. F14 નો ઉપયોગ ફેસબુક ઈન્ફ્રાસ્ટ્રક્ચરમાં મોટાભાગના પ્રકારના હેશ ટેબલના રિપ્લેસમેન્ટ તરીકે થાય છે અને પ્રભાવને બલિદાન આપ્યા વિના મેમરી વપરાશ ઘટાડી શકે છે. F14 નોંધનીય રીતે google::sparse_hash_map હેશ કોષ્ટકોને પાછળ રાખે છે, જે અત્યાર સુધી મેમરી વપરાશના સંદર્ભમાં સૌથી વધુ કાર્યક્ષમ માનવામાં આવે છે. પ્રોજેક્ટ કોડ C++ માં લખાયેલ છે અને લાઇબ્રેરીમાં શામેલ છે ફોલી.

F14 એ 14 સાથે ડબલ હેશિંગ પર આધારિત અથડામણ રિઝોલ્યુશન સિસ્ટમ સાથેના અલ્ગોરિધમનો સંદર્ભ આપે છે નમૂનાઓનો ક્રમ (14 સ્લોટની સાંકળ એક હેશ ટેબલ સેલમાં સંગ્રહિત થાય છે, અને કોષો વચ્ચેના અંતરાલની ગણતરી સહાયક હેશ ફંક્શનનો ઉપયોગ કરીને કરવામાં આવે છે). સેલ ફિલ્ટરિંગ કામગીરીને ઝડપી બનાવવા માટે, અમલીકરણ x2_86 સિસ્ટમ્સ માટે વેક્ટર સૂચના SSE64 અને Aarch64 માટે NEON નો ઉપયોગ કરે છે, જે કી ચેઈન સાથે સ્લોટ પસંદ કરવા અને સાંકળની અંદરની ચાવીઓ બહાર કાઢવા માટે કામગીરીના અમલીકરણને સમાંતર બનાવવાની મંજૂરી આપે છે. એક સમયે 14 સ્લોટના બ્લોકની પ્રક્રિયા કરવામાં આવે છે, જે પ્રોસેસર કેશનો ઉપયોગ કરવાની કાર્યક્ષમતા અને અથડામણની સંખ્યા વચ્ચેનું શ્રેષ્ઠ સંતુલન છે.

F14 ની વિશેષ વિશેષતા એ વિવિધ ડેટા સ્ટોરેજ વ્યૂહરચનાઓ પસંદ કરવાની ક્ષમતા છે:

• F14NodeMap - મોટી અને મધ્યમ કદની કી માટે ઓછામાં ઓછી મેમરી વાપરે છે. દરેક નિવેશ પર malloc ને કૉલ સાથે તત્વો પરોક્ષ રીતે સંગ્રહિત થાય છે તેની ખાતરી કરે છે;
• F14ValueMap - નાની કી માટે ન્યૂનતમ મેમરી વપરાશ પૂરો પાડે છે. તત્વો પોતે કોષોમાં સંગ્રહિત થાય છે (ઇનલાઇન). મધ્યમ અને મોટી કી માટે, આ અભિગમ નોંધપાત્ર મેમરી ઓવરહેડ તરફ દોરી જાય છે;
• F14VectorMap - મોટા કોષ્ટકો અને જટિલ કી માટે ઝડપી કામ કરે છે, પરંતુ સાદી કી અને નાની કોષ્ટકો માટે ધીમી. તત્વોને સતત વસ્તીવાળા એરેમાં પેક કરવામાં આવે છે અને 32-બીટ ઇન્ડેક્સ પોઇન્ટર દ્વારા સંબોધવામાં આવે છે;
• F14FastMap એ સંયુક્ત વ્યૂહરચના છે. જો કી 24 બાઈટ કરતા ઓછી હોય, તો F14ValueMap પસંદ કરેલ છે, અને જો વધુ, F14VectorMap પસંદ કરેલ છે.

સોર્સ: opennet.ru