تعارف
میں نے یہ رپورٹ ماسکو میں GopherCon Russia 2019 کانفرنس میں انگریزی میں اور Nizhny Novgorod میں ایک میٹنگ میں روسی زبان میں دی۔ ہم ایک بٹ میپ انڈیکس کے بارے میں بات کر رہے ہیں - B-tree سے کم عام، لیکن کم دلچسپ نہیں۔ شیئرنگ کانفرنس میں انگریزی میں تقریریں اور روسی میں متن کی نقل۔
ہم دیکھیں گے کہ بٹ میپ انڈیکس کس طرح کام کرتا ہے، یہ کب بہتر ہے، کب یہ دوسرے اشاریہ جات سے بدتر ہے، اور کن صورتوں میں یہ ان سے نمایاں طور پر تیز ہے۔ آئیے دیکھتے ہیں کہ کن مشہور ڈی بی ایم ایس کے پاس پہلے سے ہی بٹ میپ انڈیکس ہیں؛ آئیے گو میں اپنا لکھنے کی کوشش کرتے ہیں۔ اور "ڈیزرٹ کے لیے" ہم اپنا انتہائی تیز رفتار خصوصی ڈیٹا بیس بنانے کے لیے ریڈی میڈ لائبریریوں کا استعمال کریں گے۔
مجھے واقعی امید ہے کہ میرے کام آپ کے لیے مفید اور دلچسپ ہوں گے۔ جاؤ!
تعارف
سب کو سلام! شام کے چھ بج رہے ہیں اور ہم سب بہت تھک چکے ہیں۔ بورنگ ڈیٹا بیس انڈیکس تھیوری کے بارے میں بات کرنے کا بہت اچھا وقت ہے، ٹھیک ہے؟ پریشان نہ ہوں، میرے پاس یہاں اور وہاں سورس کوڈ کی دو لائنیں ہوں گی۔ 🙂
تمام لطیفے ایک طرف، رپورٹ معلومات سے بھری ہوئی ہے، اور ہمارے پاس زیادہ وقت نہیں ہے۔ تو آئیے شروع کرتے ہیں۔
آج میں مندرجہ ذیل کے بارے میں بات کروں گا:
- اشاریہ جات کیا ہیں؛
- بٹ میپ انڈیکس کیا ہے؛
- یہ کہاں استعمال ہوتا ہے اور کہاں استعمال نہیں ہوتا اور کیوں؛
- گو میں سادہ نفاذ اور کمپائلر کے ساتھ تھوڑی جدوجہد؛
- گو اسمبلر میں قدرے کم آسان، لیکن بہت زیادہ نتیجہ خیز نفاذ؛
- بٹ میپ انڈیکس کے "مسائل"؛
- موجودہ نفاذ.
تو اشاریہ جات کیا ہیں؟
انڈیکس ایک علیحدہ ڈیٹا ڈھانچہ ہے جسے ہم مرکزی ڈیٹا کے علاوہ برقرار اور اپ ڈیٹ کرتے ہیں۔ یہ تلاش کو تیز کرنے کے لیے استعمال کیا جاتا ہے۔ اشاریہ جات کے بغیر، تلاش کے لیے ڈیٹا کو مکمل طور پر جانے کی ضرورت ہوگی (ایک عمل جسے مکمل اسکین کہتے ہیں)، اور اس عمل میں لکیری الگورتھمک پیچیدگی ہوتی ہے۔ لیکن ڈیٹا بیس میں عام طور پر ڈیٹا کی بڑی مقدار ہوتی ہے اور لکیری پیچیدگی بہت سست ہوتی ہے۔ مثالی طور پر، ہم لوگارتھمک یا مستقل حاصل کریں گے۔
یہ ایک بہت ہی پیچیدہ موضوع ہے، جو باریکیوں اور تجارت سے بھرا ہوا ہے، لیکن کئی دہائیوں کے ڈیٹا بیس کی ترقی اور تحقیق کو دیکھنے کے بعد، میں یہ کہنے کے لیے تیار ہوں کہ ڈیٹا بیس کے اشاریہ جات بنانے کے لیے صرف چند وسیع پیمانے پر استعمال ہونے والے طریقے ہیں۔
پہلا نقطہ نظر تلاش کی جگہ کو درجہ بندی سے کم کرنا ہے، تلاش کی جگہ کو چھوٹے حصوں میں تقسیم کرنا ہے۔
ہم عام طور پر یہ مختلف قسم کے درختوں کا استعمال کرتے ہوئے کرتے ہیں۔ ایک مثال آپ کی الماری میں مواد کا ایک بڑا خانہ ہوگا جس میں مختلف عنوانات میں تقسیم کردہ مواد کے چھوٹے خانے ہوں گے۔ اگر آپ کو مواد کی ضرورت ہے تو، آپ شاید انہیں ایک باکس میں تلاش کریں گے جس میں "کوکیز" کہنے کے بجائے "مٹیریلز" لکھا ہو؟
دوسرا نقطہ نظر فوری طور پر مطلوبہ عنصر یا عناصر کے گروپ کو منتخب کرنا ہے۔ ہم اسے ہیش میپس یا ریورس انڈیکس میں کرتے ہیں۔ ہیش میپس کا استعمال پچھلی مثال سے بہت ملتا جلتا ہے، لیکن خانوں کے ڈبے کے بجائے، آپ کی الماری میں حتمی اشیاء کے چھوٹے چھوٹے خانوں کا ایک گروپ ہے۔
تیسرا طریقہ تلاش کی ضرورت کو ختم کرنا ہے۔ ہم یہ بلوم فلٹرز یا کوکو فلٹرز کا استعمال کرتے ہوئے کرتے ہیں۔ پہلے والے آپ کو تلاش کرنے سے بچاتے ہوئے فوری طور پر جواب دیتے ہیں۔
آخری نقطہ نظر یہ ہے کہ جدید ہارڈ ویئر ہمیں فراہم کردہ تمام طاقت کا بھرپور استعمال کریں۔ یہ بالکل وہی ہے جو ہم بٹ میپ انڈیکس میں کرتے ہیں۔ ہاں، ان کا استعمال کرتے وقت ہمیں بعض اوقات پورے انڈیکس سے گزرنا پڑتا ہے، لیکن ہم اسے انتہائی مؤثر طریقے سے کرتے ہیں۔
جیسا کہ میں نے کہا، ڈیٹا بیس انڈیکس کا موضوع وسیع اور سمجھوتوں سے بھرا ہوا ہے۔ اس کا مطلب یہ ہے کہ بعض اوقات ہم ایک ہی وقت میں کئی طریقوں کا استعمال کر سکتے ہیں: اگر ہمیں تلاش کو مزید تیز کرنے کی ضرورت ہے، یا اگر ہمیں تلاش کی تمام ممکنہ اقسام کا احاطہ کرنے کی ضرورت ہے۔
آج میں ان میں سے سب سے کم معلوم نقطہ نظر کے بارے میں بات کروں گا - بٹ میپ انڈیکس۔
میں اس موضوع پر بات کرنے والا کون ہوں؟
میں Badoo میں ٹیم لیڈ کے طور پر کام کرتا ہوں (شاید آپ ہماری دوسری پروڈکٹ، Bumble سے زیادہ واقف ہوں)۔ ہمارے پاس پہلے ہی دنیا بھر میں 400 ملین سے زیادہ صارفین ہیں اور بہت سی خصوصیات ہیں جو ان کے لیے بہترین میچ کا انتخاب کرتی ہیں۔ ہم یہ حسب ضرورت خدمات کا استعمال کرتے ہوئے کرتے ہیں، بشمول بٹ میپ انڈیکس۔
تو بٹ میپ انڈیکس کیا ہے؟
بٹ میپ انڈیکس، جیسا کہ نام سے پتہ چلتا ہے، سرچ انڈیکس کو لاگو کرنے کے لیے بٹ میپ یا بٹ سیٹس کا استعمال کریں۔ برڈز آئی ویو سے، یہ انڈیکس ایک یا زیادہ ایسے بٹ میپس پر مشتمل ہوتا ہے جو کسی بھی ہستی (جیسے لوگ) اور ان کی خصوصیات یا پیرامیٹرز (عمر، آنکھوں کا رنگ، وغیرہ) کی نمائندگی کرتے ہیں، اور بٹ آپریشنز (AND, OR, NOT) کا استعمال کرتے ہوئے الگورتھم تلاش کے سوال کا جواب دینے کے لیے۔
ہمیں بتایا گیا ہے کہ بٹ میپ اشاریہ جات ایسے معاملات کے لیے بہترین موزوں اور انتہائی پرفارمنس ہیں جہاں ایسی تلاشیں ہیں جو بہت سے کم کارڈینیلیٹی کالمز میں سوالات کو یکجا کرتی ہیں (سوچیں "آنکھوں کا رنگ" یا "ازدواجی حیثیت" بمقابلہ "شہر کے مرکز سے فاصلہ")۔ لیکن میں بعد میں دکھاؤں گا کہ وہ اعلی کارڈینیلیٹی کالموں کے لیے بھی ٹھیک کام کرتے ہیں۔
آئیے بٹ میپ انڈیکس کی آسان ترین مثال دیکھتے ہیں۔
تصور کریں کہ ہمارے پاس ماسکو کے ریستوراں کی فہرست ہے جس میں بائنری خصوصیات ہیں:
- میٹرو کے قریب؛
- نجی پارکنگ ہے؛
- وہاں ایک برآمدہ ہے (چھت ہے)؛
- آپ ایک میز ریزرو کر سکتے ہیں (ریزرویشن قبول کرتا ہے)؛
- سبزی خوروں کے لیے موزوں (ویگن دوستانہ)؛
- مہنگا (مہنگا)
آئیے ہر ریستوراں کو 0 سے شروع ہونے والا ایک ترتیب نمبر دیں اور 6 بٹ میپس (ہر خصوصیت کے لیے ایک) کے لیے میموری مختص کریں۔ پھر ہم ان بٹ میپس کو اس بات پر منحصر کریں گے کہ آیا ریستوران کے پاس یہ پراپرٹی ہے یا نہیں۔ اگر ریستوراں 4 میں برآمدہ ہے، تو بٹ نمبر 4 میں "ایک برآمدہ ہے" بٹ میپ 1 پر سیٹ کیا جائے گا (اگر کوئی برآمدہ نہیں ہے تو 0 پر)۔
اب ہمارے پاس سب سے آسان بٹ میپ انڈیکس ہے، اور ہم اسے سوالات کا جواب دینے کے لیے استعمال کر سکتے ہیں جیسے:
- "مجھے سبزی خور دوستانہ ریستوراں دکھائیں"؛
- "مجھے برآمدے کے ساتھ سستے ریستوراں دکھائیں جہاں آپ ایک میز ریزرو کر سکتے ہیں۔"
کیسے؟ آئیے ایک نظر ڈالتے ہیں۔ پہلی درخواست بہت آسان ہے۔ ہمیں بس "سبزی خور دوست" بٹ میپ لینے کی ضرورت ہے اور اسے ان ریستورانوں کی فہرست میں تبدیل کرنا ہے جن کے بٹس سامنے آئے ہیں۔
دوسری درخواست کچھ زیادہ ہی پیچیدہ ہے۔ ہمیں سستے ریستورانوں کی فہرست حاصل کرنے کے لیے "مہنگے" بٹ میپ پر NOT بٹ میپ استعمال کرنے کی ضرورت ہے، پھر اور اسے "کیا میں ایک ٹیبل بک کر سکتا ہوں" بٹ میپ کے ساتھ، اور نتیجہ "وہاں ایک برآمدہ ہے" بٹ میپ کے ساتھ۔ نتیجے میں آنے والا بٹ میپ ان اداروں کی فہرست پر مشتمل ہوگا جو ہمارے تمام معیارات پر پورا اترتے ہیں۔ اس مثال میں، یہ صرف Yunost ریستوراں ہے۔
اس میں بہت ساری تھیوری شامل ہے، لیکن پریشان نہ ہوں، ہم بہت جلد کوڈ دیکھیں گے۔
بٹ میپ انڈیکس کہاں استعمال ہوتے ہیں؟
اگر آپ گوگل بٹ میپ انڈیکس کرتے ہیں، تو 90% جوابات کسی نہ کسی طریقے سے اوریکل ڈی بی سے متعلق ہوں گے۔ لیکن دوسرے ڈی بی ایم ایس بھی شاید ایسی ٹھنڈی چیز کی حمایت کرتے ہیں، ٹھیک ہے؟ واقعی نہیں۔
آئیے مرکزی ملزمان کی فہرست پر غور کریں۔
MySQL ابھی تک بٹ میپ اشاریہ جات کو سپورٹ نہیں کرتا ہے، لیکن اس آپشن کو شامل کرنے کی تجویز پیش کی گئی ہے ().
PostgreSQL بٹ میپ اشاریہ جات کی حمایت نہیں کرتا ہے، لیکن متعدد دیگر اشاریہ جات میں تلاش کے نتائج کو یکجا کرنے کے لیے سادہ بٹ میپس اور بٹ آپریشنز کا استعمال کرتا ہے۔
Tarantool میں بٹ سیٹ اشاریہ جات ہیں اور ان پر سادہ تلاش کی حمایت کرتا ہے۔
ریڈیس میں سادہ بٹ فیلڈز ہیں۔) ان کو تلاش کرنے کی صلاحیت کے بغیر۔
MongoDB ابھی تک بٹ میپ اشاریہ جات کو سپورٹ نہیں کرتا ہے، لیکن ایک تجویز بھی ہے کہ اس آپشن کو شامل کیا جائے۔
Elasticsearch اندرونی طور پر بٹ میپس کا استعمال کرتی ہے۔).
- لیکن ہمارے گھر میں ایک نیا پڑوسی نمودار ہوا ہے: پیلوسا۔ یہ گو میں لکھا ہوا ایک نیا غیر متعلقہ ڈیٹا بیس ہے۔ یہ صرف بٹ میپ انڈیکس پر مشتمل ہے اور ان پر ہر چیز کی بنیاد رکھتا ہے۔ ہم اس پر تھوڑی دیر بعد بات کریں گے۔
گو میں نفاذ
لیکن بٹ میپ انڈیکس اتنے شاذ و نادر ہی کیوں استعمال ہوتے ہیں؟ اس سوال کا جواب دینے سے پہلے، میں آپ کو دکھانا چاہوں گا کہ گو میں ایک بہت ہی آسان بٹ میپ انڈیکس کو کیسے نافذ کیا جائے۔
بٹ میپس بنیادی طور پر صرف ڈیٹا کے ٹکڑے ہوتے ہیں۔ گو میں، آئیے اس کے لیے بائٹ سلائسز استعمال کریں۔
ہمارے پاس ایک ریستوران کی خصوصیت کے لیے ایک بٹ میپ ہے، اور بٹ میپ میں ہر ایک بٹ اس بات کی نشاندہی کرتا ہے کہ آیا کسی خاص ریستوراں میں یہ پراپرٹی ہے یا نہیں۔
ہمیں دو مددگار افعال کی ضرورت ہوگی۔ ایک کا استعمال ہمارے بٹ میپس کو بے ترتیب ڈیٹا سے بھرنے کے لیے کیا جائے گا۔ بے ترتیب، لیکن ایک خاص امکان کے ساتھ کہ ریستوراں میں ہر ایک پراپرٹی ہے۔ مثال کے طور پر، مجھے یقین ہے کہ ماسکو میں بہت کم ایسے ریستوراں ہیں جہاں آپ ٹیبل نہیں رکھ سکتے، اور مجھے لگتا ہے کہ تقریباً 20% ادارے سبزی خوروں کے لیے موزوں ہیں۔
دوسرا فنکشن بٹ میپ کو ریستوران کی فہرست میں تبدیل کر دے گا۔
سوال کا جواب دینے کے لیے "مجھے ایسے سستے ریستوراں دکھائیں جن میں پیٹیو ہو اور وہ ریزرویشن کر سکیں"، ہمیں دو بٹ آپریشنز کی ضرورت ہے: نہیں اور اور۔
ہم زیادہ پیچیدہ اور نہیں آپریٹر کا استعمال کرکے اپنے کوڈ کو تھوڑا سا آسان بنا سکتے ہیں۔
ہمارے پاس ان آپریشنز میں سے ہر ایک کے لیے افعال ہیں۔ وہ دونوں سلائسوں سے گزرتے ہیں، ہر ایک سے متعلقہ عناصر لیتے ہیں، انہیں تھوڑا سا آپریشن کے ساتھ یکجا کرتے ہیں اور نتیجہ کو نتیجے میں سلائس میں ڈالتے ہیں.
اور اب ہم اپنے بٹ میپس اور فنکشنز کو تلاش کے سوال کا جواب دینے کے لیے استعمال کر سکتے ہیں۔
کارکردگی اتنی زیادہ نہیں ہے، حالانکہ فنکشنز بہت آسان ہیں اور ہم نے ہر بار فنکشن کو بلانے پر ایک نیا نتیجہ خیز سلائس واپس نہ کرکے کافی رقم بچائی ہے۔
pprof کے ساتھ تھوڑا سا پروفائلنگ کرنے کے بعد، میں نے دیکھا کہ گو کمپائلر میں ایک بہت ہی آسان لیکن بہت اہم آپٹیمائزیشن غائب تھی: فنکشن ان لائننگ۔
حقیقت یہ ہے کہ گو کمپائلر ان لوپس سے بہت ڈرتا ہے جو سلائسوں سے گزرتے ہیں، اور واضح طور پر ان لائن فنکشنز سے انکار کرتے ہیں جن میں ایسے لوپس ہوتے ہیں۔
لیکن میں خوفزدہ نہیں ہوں اور میں اچھے پرانے دنوں کی طرح لوپ کے بجائے گوٹو کا استعمال کرکے کمپائلر کو بیوقوف بنا سکتا ہوں۔
اور، جیسا کہ آپ دیکھ سکتے ہیں، اب کمپائلر خوشی سے ہمارے فنکشن کو ان لائن کرے گا! نتیجے کے طور پر، ہم تقریباً 2 مائیکرو سیکنڈز بچانے کا انتظام کرتے ہیں۔ برا نہیں ہے!
دوسری رکاوٹ یہ دیکھنا آسان ہے کہ کیا آپ اسمبلی آؤٹ پٹ کو قریب سے دیکھتے ہیں۔ مرتب کرنے والے نے ہمارے سب سے مشہور لوپ کے اندر ایک سلائس باؤنڈری چیک شامل کیا۔ حقیقت یہ ہے کہ گو ایک محفوظ زبان ہے، مرتب کرنے والے کو ڈر ہے کہ میرے تین دلائل (تین سلائس) مختلف سائز کے ہیں۔ سب کے بعد، پھر ایک نام نہاد بفر اوور فلو کی موجودگی کا ایک نظریاتی امکان ہو گا.
آئیے کمپائلر کو یہ دکھا کر یقین دلاتے ہیں کہ تمام سلائس ایک ہی سائز کے ہیں۔ ہم اپنے فنکشن کے آغاز میں ایک سادہ چیک شامل کرکے ایسا کرسکتے ہیں۔
یہ دیکھ کر، مرتب کرنے والا خوشی سے چیک چھوڑ دیتا ہے، اور ہم مزید 500 نینو سیکنڈ بچاتے ہیں۔
بڑے قصائی
ٹھیک ہے، ہم نے اپنے سادہ نفاذ سے کچھ کارکردگی کو نچوڑ لیا، لیکن یہ نتیجہ درحقیقت موجودہ ہارڈ ویئر کے ساتھ ممکن ہونے سے کہیں زیادہ خراب ہے۔
ہم صرف بنیادی بٹ آپریشنز کرتے ہیں، اور ہمارے پروسیسرز انہیں بہت مؤثر طریقے سے انجام دیتے ہیں۔ لیکن، بدقسمتی سے، ہم اپنے پروسیسر کو بہت چھوٹے کام کے ساتھ "کھانا" دیتے ہیں۔ ہمارے افعال بائٹ بائی بائٹ کی بنیاد پر کام کرتے ہیں۔ ہم UInt8 سلائسز کا استعمال کرتے ہوئے 64 بائٹ ٹکڑوں کے ساتھ کام کرنے کے لیے اپنے کوڈ کو بہت آسانی سے موافقت کر سکتے ہیں۔
جیسا کہ آپ دیکھ سکتے ہیں، اس چھوٹی سی تبدیلی نے بیچ کے سائز کو آٹھ گنا بڑھا کر ہمارے پروگرام کو آٹھ گنا بڑھا دیا۔ حاصل کو لکیری کہا جا سکتا ہے۔
اسمبلر میں نفاذ
لیکن یہ آخر نہیں ہے۔ ہمارے پروسیسر 16، 32 اور یہاں تک کہ 64 بائٹس کے ٹکڑوں کے ساتھ کام کر سکتے ہیں۔ اس طرح کے "وسیع" آپریشنز کو سنگل انسٹرکشن ملٹیپل ڈیٹا (SIMD؛ ایک انسٹرکشن، بہت سے ڈیٹا) کہا جاتا ہے، اور کوڈ کو تبدیل کرنے کے عمل کو اس طرح کے آپریشنز کو ویکٹرائزیشن کہا جاتا ہے۔
بدقسمتی سے، گو کمپائلر ویکٹرائزیشن میں بہترین نہیں ہے۔ فی الحال، Go کوڈ کو ویکٹرائز کرنے کا واحد طریقہ یہ ہے کہ Go assembler کا استعمال کرتے ہوئے ان کارروائیوں کو دستی طور پر لیا جائے۔
گو جمع کرنے والا ایک عجیب حیوان ہے۔ آپ شاید جانتے ہوں گے کہ اسمبلی لینگویج ایک ایسی چیز ہے جو آپ جس کمپیوٹر کے لیے لکھ رہے ہیں اس کے فن تعمیر سے بہت زیادہ جڑی ہوئی ہے، لیکن گو میں ایسا نہیں ہے۔ گو اسمبلر زیادہ IRL (انٹرمیڈیٹ نمائندگی کی زبان) یا انٹرمیڈیٹ لینگویج کی طرح ہے: یہ عملی طور پر پلیٹ فارم سے آزاد ہے۔ روب پائیک نے شاندار پرفارمنس دی۔ اس موضوع پر کئی سال پہلے ڈینور میں GopherCon میں۔
اس کے علاوہ، Go ایک غیر معمولی پلان 9 فارمیٹ استعمال کرتا ہے، جو عام طور پر قبول شدہ AT&T اور Intel فارمیٹس سے مختلف ہے۔
یہ کہنا محفوظ ہے کہ Go assembler کو ہاتھ سے لکھنا سب سے زیادہ مزہ نہیں ہے۔
لیکن، خوش قسمتی سے، پہلے ہی دو اعلیٰ سطحی ٹولز موجود ہیں جو Go assembler لکھنے میں ہماری مدد کرتے ہیں: PeachPy اور avo۔ دونوں افادیتیں بالترتیب Python اور Go میں لکھے گئے اعلیٰ سطحی کوڈ سے Go اسمبلر تیار کرتی ہیں۔
یہ افادیتیں رجسٹر ایلوکیشن، رائٹنگ لوپس جیسی چیزوں کو آسان بناتی ہیں اور عام طور پر گو میں اسمبلی پروگرامنگ کی دنیا میں جانے کے عمل کو آسان بناتی ہیں۔
ہم ایوو استعمال کریں گے، اس لیے ہمارے پروگرام تقریباً باقاعدہ گو پروگرام ہوں گے۔
ایوو پروگرام کی سب سے آسان مثال یہی نظر آتی ہے۔ ہمارے پاس ایک مین () فنکشن ہے، جو اپنے اندر Add() فنکشن کی وضاحت کرتا ہے، جس کا مطلب ہے دو نمبروں کا اضافہ کرنا۔ نام کے مطابق پیرامیٹرز حاصل کرنے اور مفت اور موزوں پروسیسر رجسٹروں میں سے ایک حاصل کرنے کے لیے یہاں مددگار فنکشنز ہیں۔ ہر پروسیسر آپریشن کا ایک متعلقہ فنکشن ایوو پر ہوتا ہے، جیسا کہ ADDQ میں دیکھا گیا ہے۔ آخر میں، ہم نتیجے کی قدر کو ذخیرہ کرنے کے لیے ایک مددگار فنکشن دیکھتے ہیں۔
گو جنریٹ کو کال کرنے سے، ہم پروگرام کو ایوو پر عمل میں لائیں گے اور اس کے نتیجے میں، دو فائلیں تیار ہوں گی:
- گو اسمبلر میں نتیجے والے کوڈ کے ساتھ add.s؛
- دو دنیاؤں کو جوڑنے کے لیے فنکشن ہیڈر کے ساتھ stub.go: Go and assembler.
اب جب کہ ہم نے دیکھا ہے کہ avo کیا کرتا ہے اور کیسے، آئیے اپنے افعال کو دیکھتے ہیں۔ میں نے فنکشنز کے دونوں اسکیلر اور ویکٹر (SIMD) ورژن کو لاگو کیا۔
آئیے پہلے اسکیلر ورژن دیکھیں۔
جیسا کہ پچھلی مثال میں ہے، ہم ایک مفت اور درست عام مقصد کے رجسٹر کے لیے کہہ رہے ہیں، ہمیں دلائل کے لیے آفسیٹ اور سائز کا حساب لگانے کی ضرورت نہیں ہے۔ ایوو یہ سب ہمارے لیے کرتا ہے۔
ہم کارکردگی کو بہتر بنانے اور گو کمپائلر کو چال کرنے کے لیے لیبلز اور گوٹو (یا جمپس) استعمال کرتے تھے، لیکن اب ہم اسے شروع سے ہی کر رہے ہیں۔ نقطہ یہ ہے کہ سائیکل ایک اعلی سطحی تصور ہے۔ جمع کرنے والے میں، ہمارے پاس صرف لیبل اور چھلانگیں ہیں۔
باقی کوڈ پہلے سے ہی واقف اور قابل فہم ہونا چاہئے۔ ہم لیبلز اور چھلانگوں کے ساتھ ایک لوپ کی تقلید کرتے ہیں، اپنے دو سلائسز سے ڈیٹا کا ایک چھوٹا ٹکڑا لیتے ہیں، انہیں تھوڑا سا آپریشن (اور اس معاملے میں نہیں) کے ساتھ جوڑتے ہیں اور پھر نتیجہ کو آنے والے سلائس میں ڈالتے ہیں۔ تمام
حتمی جمع کرنے والا کوڈ ایسا لگتا ہے۔ ہمیں آفسیٹس اور سائز (سبز رنگ میں نمایاں) کا حساب نہیں لگانا تھا یا استعمال شدہ رجسٹروں کا ٹریک رکھنے کی ضرورت نہیں تھی (سرخ رنگ میں نمایاں)۔
اگر ہم اسمبلی زبان کے نفاذ کی کارکردگی کا موازنہ گو میں بہترین نفاذ کی کارکردگی سے کریں، تو ہم دیکھیں گے کہ یہ ایک جیسا ہے۔ اور یہ متوقع ہے۔ سب کے بعد، ہم نے کچھ خاص نہیں کیا - ہم نے صرف دوبارہ پیش کیا کہ ایک گو کمپائلر کیا کرے گا.
بدقسمتی سے، ہم کمپائلر کو اسمبلی کی زبان میں لکھے گئے اپنے فنکشنز کو ان لائن کرنے پر مجبور نہیں کر سکتے۔ گو کمپائلر میں فی الحال ایسی کوئی خصوصیت نہیں ہے، حالانکہ کافی عرصے سے اسے شامل کرنے کی درخواست کی جا رہی ہے۔
یہی وجہ ہے کہ اسمبلی کی زبان میں چھوٹے افعال سے کوئی فائدہ حاصل کرنا ناممکن ہے۔ ہمیں یا تو بڑے فنکشن لکھنے کی ضرورت ہے، یا نیا ریاضی/بٹس پیکیج استعمال کرنا ہوگا، یا اسمبلر لینگویج کو نظرانداز کرنا ہوگا۔
آئیے اب اپنے فنکشنز کے ویکٹر ورژن کو دیکھتے ہیں۔
اس مثال کے لیے، میں نے AVX2 استعمال کرنے کا فیصلہ کیا، لہذا ہم ایسے آپریشنز استعمال کریں گے جو 32-بائٹ ٹکڑوں پر چلتے ہیں۔ کوڈ کی ساخت اسکیلر ورژن سے بہت ملتی جلتی ہے: پیرامیٹرز لوڈ کرنا، مفت مشترکہ رجسٹر طلب کرنا، وغیرہ۔
ایک اختراع یہ ہے کہ وسیع تر ویکٹر آپریشنز خصوصی وسیع رجسٹر استعمال کرتے ہیں۔ 32 بائٹ ٹکڑوں کی صورت میں، یہ Y کے ساتھ پہلے سے لگے ہوئے رجسٹر ہیں۔ یہی وجہ ہے کہ آپ کوڈ میں YMM() فنکشن نظر آتے ہیں۔ اگر میں AVX-512 64 بٹ ٹکڑوں کے ساتھ استعمال کر رہا ہوں تو، سابقہ Z ہوگا۔
دوسری جدت یہ ہے کہ میں نے لوپ انرولنگ نامی ایک آپٹیمائزیشن استعمال کرنے کا فیصلہ کیا، جس کا مطلب ہے کہ لوپ کے آغاز پر کودنے سے پہلے دستی طور پر آٹھ لوپ آپریشن کرنا۔ یہ اصلاح کوڈ میں شاخوں کی تعداد کو کم کرتی ہے، اور دستیاب مفت رجسٹروں کی تعداد تک محدود ہے۔
ٹھیک ہے، کارکردگی کا کیا ہوگا؟ وہ خوبصورت ہے! ہم نے بہترین Go حل کے مقابلے میں تقریباً سات گنا رفتار حاصل کی۔ متاثر کن، ٹھیک ہے؟
لیکن یہاں تک کہ استفسار کے شیڈولر کے لیے AVX-512، prefetching یا JIT (صرف وقت میں کمپائلر) کا استعمال کرکے اس عمل کو ممکنہ طور پر تیز کیا جا سکتا ہے۔ لیکن یہ یقینی طور پر ایک علیحدہ رپورٹ کا موضوع ہے۔
بٹ میپ انڈیکس کے ساتھ مسائل
اب جب کہ ہم گو میں بٹ میپ انڈیکس کے سادہ نفاذ اور اسمبلی لینگویج میں بہت زیادہ نتیجہ خیز کو دیکھ چکے ہیں، آئیے آخر میں اس بارے میں بات کرتے ہیں کہ بٹ میپ انڈیکس اتنا کم ہی کیوں استعمال ہوتا ہے۔
پرانے کاغذات بٹ میپ انڈیکس کے ساتھ تین مسائل کا ذکر کرتے ہیں، لیکن نئے کاغذات اور میں بحث کرتا ہوں کہ وہ اب متعلقہ نہیں ہیں۔ ہم ان میں سے ہر ایک مسئلے میں گہرائی میں نہیں جائیں گے، بلکہ ان کو سطحی طور پر دیکھیں گے۔
ہائی کارڈنلٹی کا مسئلہ
لہذا، ہمیں بتایا گیا ہے کہ بٹ میپ انڈیکس صرف کم کارڈینیلیٹی والے فیلڈز کے لیے موزوں ہیں، یعنی وہ جن کی قدریں کم ہیں (مثال کے طور پر جنس یا آنکھوں کا رنگ)، اور اس کی وجہ یہ ہے کہ ایسے فیلڈز کی معمول کی نمائندگی (ایک bit per value) زیادہ کارڈینیلیٹی کی صورت میں، یہ بہت زیادہ جگہ لے گا اور مزید یہ کہ، یہ بٹ میپ انڈیکس خراب (شاذ و نادر ہی) بھرے ہوں گے۔
بعض اوقات ہم ایک مختلف نمائندگی کا استعمال کر سکتے ہیں، جیسا کہ وہ معیاری جو ہم اعداد کی نمائندگی کے لیے استعمال کرتے ہیں۔ لیکن یہ کمپریشن الگورتھم کی آمد تھی جس نے سب کچھ بدل دیا۔ پچھلی دہائیوں میں، سائنسدانوں اور محققین نے بٹ میپس کے لیے بڑی تعداد میں کمپریشن الگورتھم تیار کیے ہیں۔ ان کا بنیادی فائدہ یہ ہے کہ بٹ آپریشن کرنے کے لیے بٹ میپس کو ڈی کمپریس کرنے کی ضرورت نہیں ہے - ہم بٹ آپریشن براہ راست کمپریسڈ بٹ میپس پر کر سکتے ہیں۔
حال ہی میں، ہائبرڈ نقطہ نظر ظاہر ہونا شروع ہو گیا ہے، جیسے گرجنے والے بٹ میپس۔ وہ بیک وقت بٹ میپس کے لیے تین مختلف نمائندگیوں کا استعمال کرتے ہیں - بذات خود بٹ میپس، اری اور نام نہاد بٹ رنز - اور کارکردگی کو زیادہ سے زیادہ کرنے اور میموری کی کھپت کو کم سے کم کرنے کے لیے ان کے درمیان توازن قائم کرتے ہیں۔
آپ مقبول ترین ایپلیکیشنز میں گرجتے ہوئے بٹ میپس تلاش کر سکتے ہیں۔ پروگرامنگ زبانوں کی وسیع اقسام کے لیے پہلے سے ہی ایک بڑی تعداد میں نفاذ موجود ہیں، بشمول Go کے لیے تین سے زیادہ نفاذ۔
ایک اور نقطہ نظر جو ہمیں اعلی کارڈینیلیٹی سے نمٹنے میں مدد کرسکتا ہے اسے بائننگ کہتے ہیں۔ تصور کریں کہ آپ کے پاس ایک فیلڈ ہے جو کسی شخص کے قد کی نمائندگی کرتا ہے۔ اونچائی ایک تیرتا ہوا پوائنٹ نمبر ہے، لیکن ہم انسان اس کے بارے میں اس طرح نہیں سوچتے ہیں۔ ہمارے لیے اونچائی 185,2 سینٹی میٹر اور 185,3 سینٹی میٹر میں کوئی فرق نہیں ہے۔
یہ پتہ چلتا ہے کہ ہم 1 سینٹی میٹر کے اندر گروپوں میں ایک جیسی اقدار کو گروپ کر سکتے ہیں۔
اور اگر ہم یہ بھی جانتے ہیں کہ بہت کم لوگ 50 سینٹی میٹر سے چھوٹے اور 250 سینٹی میٹر سے زیادہ لمبے ہوتے ہیں، تو ہم بنیادی طور پر لامحدود کارڈنالٹی والی فیلڈ کو تقریباً 200 اقدار کی کارڈنالٹی والی فیلڈ میں تبدیل کر سکتے ہیں۔
یقینا، اگر ضروری ہو تو، ہم بعد میں اضافی فلٹرنگ کر سکتے ہیں۔
ہائی بینڈوتھ کا مسئلہ
بٹ میپ انڈیکس کے ساتھ اگلا مسئلہ یہ ہے کہ ان کو اپ ڈیٹ کرنا بہت مہنگا پڑ سکتا ہے۔
ڈیٹا بیس کو ڈیٹا کو اپ ڈیٹ کرنے کے قابل ہونا چاہیے جب کہ ممکنہ طور پر سینکڑوں دیگر سوالات ڈیٹا کو تلاش کر رہے ہیں۔ ہم وقتی ڈیٹا تک رسائی یا اشتراک کے دیگر مسائل سے بچنے کے لیے ہمیں تالے کی ضرورت ہے۔ اور جہاں ایک بڑا تالا ہے، وہاں ایک مسئلہ ہے - تالے کا تنازعہ، جب یہ تالا ایک رکاوٹ بن جاتا ہے۔
اس مسئلے کو شارڈنگ کا استعمال کرتے ہوئے یا ورژن شدہ اشاریہ جات کا استعمال کرکے حل کیا جاسکتا ہے۔
شارڈنگ ایک سادہ اور معروف چیز ہے۔ آپ بٹ میپ انڈیکس کو شارڈ کرسکتے ہیں جیسا کہ آپ کسی دوسرے ڈیٹا کو کرتے ہیں۔ ایک بڑے تالے کے بجائے، آپ کو چھوٹے تالے کا ایک گچھا مل جائے گا اور اس طرح تالے کے جھگڑے سے چھٹکارا پائیں گے۔
مسئلہ کو حل کرنے کا دوسرا طریقہ ورژن شدہ اشاریہ جات کا استعمال کرنا ہے۔ آپ کے پاس انڈیکس کی ایک کاپی ہو سکتی ہے جسے آپ تلاش یا پڑھنے کے لیے استعمال کرتے ہیں، اور ایک کاپی جسے آپ لکھنے یا اپ ڈیٹ کرنے کے لیے استعمال کرتے ہیں۔ اور ایک بار ایک مخصوص مدت میں (مثال کے طور پر، ہر 100 ms یا 500 ms میں ایک بار) آپ ان کی نقل بناتے ہیں اور انہیں تبدیل کرتے ہیں۔ بلاشبہ، یہ نقطہ نظر صرف ان صورتوں میں لاگو ہوتا ہے جہاں آپ کی ایپلیکیشن قدرے پیچھے رہنے والے سرچ انڈیکس کو سنبھال سکتی ہے۔
ان دونوں طریقوں کو بیک وقت استعمال کیا جا سکتا ہے: آپ کے پاس شارڈ ورژن والا انڈیکس ہو سکتا ہے۔
مزید پیچیدہ سوالات
بٹ میپ اشاریہ جات کے ساتھ حتمی مسئلہ یہ ہے کہ ہمیں بتایا جاتا ہے کہ وہ زیادہ پیچیدہ قسم کے سوالات، جیسے اسپین کے سوالات کے لیے موزوں نہیں ہیں۔
درحقیقت، اگر آپ اس کے بارے میں سوچتے ہیں، تو AND، OR، وغیرہ جیسے بٹ آپریشنز سوالات کے لیے بہت موزوں نہیں ہیں a la "مجھے ہوٹل دکھائیں جن کے کمرے کے نرخ 200 سے 300 ڈالر فی رات ہیں۔"
ایک سادہ اور غیر دانشمندانہ حل یہ ہو گا کہ ہر ڈالر کی قیمت کے نتائج لیں اور انہیں بٹ وائز یا آپریشن کے ساتھ جوڑ دیں۔
تھوڑا بہتر حل گروپ بندی کا استعمال کرنا ہوگا۔ مثال کے طور پر، 50 ڈالر کے گروپوں میں۔ یہ ہمارے عمل کو 50 گنا تیز کر دے گا۔
لیکن خاص طور پر اس قسم کی درخواست کے لیے بنائے گئے ایک منظر کا استعمال کرکے بھی مسئلہ آسانی سے حل ہو جاتا ہے۔ سائنسی کاغذات میں اسے رینج انکوڈڈ بٹ میپس کہا جاتا ہے۔
اس نمائندگی میں، ہم کچھ قدر (مثال کے طور پر، 200) کے لیے صرف ایک بٹ سیٹ نہیں کرتے ہیں، بلکہ اس قدر اور ہر چیز کو زیادہ سیٹ کرتے ہیں۔ 200 اور اس سے اوپر۔ 300: 300 اور اس سے اوپر کے لیے ایک جیسا۔ اور اسی طرح.
اس نمائندگی کا استعمال کرتے ہوئے، ہم صرف دو بار انڈیکس کو عبور کرکے اس قسم کی تلاش کے سوال کا جواب دے سکتے ہیں۔ سب سے پہلے، ہم ان ہوٹلوں کی فہرست حاصل کریں گے جہاں کمرے کی قیمت کم یا $300 ہے، اور پھر ہم اس سے ان ہوٹلوں کو ہٹا دیں گے جہاں کمرے کی قیمت کم یا $199 ہے۔ تیار.
آپ حیران ہوں گے، لیکن بٹ میپ انڈیکس کا استعمال کرتے ہوئے جیوکوریز بھی ممکن ہیں۔ چال یہ ہے کہ ایک جیومیٹرک نمائندگی کا استعمال کیا جائے جو آپ کے کوآرڈینیٹ کو ہندسی شکل کے ساتھ گھیرے ہوئے ہو۔ مثال کے طور پر، گوگل سے S2۔ اعداد و شمار کو تین یا اس سے زیادہ کاٹتی ہوئی لکیروں کی شکل میں ظاہر کرنا ممکن ہونا چاہیے جنہیں نمبر دیا جا سکتا ہے۔ اس طرح ہم اپنی جیوکوری کو "خالی کے ساتھ" (ان نمبر والی لائنوں کے ساتھ) کئی سوالات میں تبدیل کر سکتے ہیں۔
تیار کردہ حل
مجھے امید ہے کہ میں نے آپ کو تھوڑی دلچسپی لی ہے اور اب آپ کے پاس اپنے ہتھیاروں میں ایک اور کارآمد ٹول ہے۔ اگر آپ کو کبھی بھی ایسا کچھ کرنے کی ضرورت ہے، تو آپ کو معلوم ہو جائے گا کہ کس طرف دیکھنا ہے۔
تاہم، ہر کسی کے پاس شروع سے بٹ میپ انڈیکس بنانے کے لیے وقت، صبر، یا وسائل نہیں ہوتے۔ خاص طور پر زیادہ جدید، مثال کے طور پر، SIMD کا استعمال کرتے ہوئے.
خوش قسمتی سے، آپ کی مدد کے لیے کئی تیار حل موجود ہیں۔
گرجتے ہوئے بٹ میپس
سب سے پہلے، وہی گرجنے والی بٹ میپس لائبریری ہے جس کے بارے میں میں پہلے ہی بات کر چکا ہوں۔ اس میں تمام ضروری کنٹینرز اور بٹ آپریشنز شامل ہیں جن کی آپ کو ایک مکمل بٹ میپ انڈیکس بنانے کی ضرورت ہوگی۔
بدقسمتی سے، اس وقت، Go کے نفاذ میں سے کوئی بھی SIMD کا استعمال نہیں کرتا، جس کا مطلب ہے کہ Go کے نفاذ C کے نفاذ سے کم کارکردگی کا مظاہرہ کرتے ہیں، مثال کے طور پر۔
پیلوسا
ایک اور پروڈکٹ جو آپ کی مدد کر سکتی ہے وہ ہے Pilosa DBMS، جس میں درحقیقت صرف بٹ میپ انڈیکس ہوتے ہیں۔ یہ نسبتاً نیا حل ہے، لیکن یہ بڑی رفتار سے دل جیت رہا ہے۔
Pilosa اندرونی طور پر roaring bitmaps کا استعمال کرتا ہے اور آپ کو ان کو استعمال کرنے، آسان بنانے اور ان تمام چیزوں کی وضاحت کرتا ہے جن کے بارے میں میں نے اوپر بات کی: گروپ بندی، رینج انکوڈ شدہ بٹ میپس، فیلڈ کا تصور، وغیرہ۔
آئیے اس سوال کا جواب دینے کے لیے Pilosa کے استعمال کی ایک مثال پر ایک سرسری نظر ڈالتے ہیں جس سے آپ پہلے سے واقف ہیں۔
مثال اس سے بہت ملتی جلتی ہے جو آپ نے پہلے دیکھی تھی۔ ہم Pilosa سرور پر ایک کلائنٹ بناتے ہیں، ایک انڈیکس اور ضروری فیلڈز بناتے ہیں، پھر اپنے فیلڈز کو بے ترتیب ڈیٹا سے امکانات کے ساتھ بھرتے ہیں اور آخر میں، واقف استفسار کو انجام دیتے ہیں۔
اس کے بعد، ہم "مہنگی" فیلڈ پر NOT کا استعمال کرتے ہیں، پھر نتیجہ (یا AND اسے) "ٹیرس" فیلڈ اور "ریزرویشنز" فیلڈ کے ساتھ کاٹتے ہیں۔ اور آخر کار، ہمیں حتمی نتیجہ ملتا ہے۔
میں واقعی امید کرتا ہوں کہ مستقبل قریب میں یہ نئی قسم کا انڈیکس DBMSs جیسے MySQL اور PostgreSQL - bitmap indexes میں بھی ظاہر ہوگا۔
حاصل يہ ہوا
اگر آپ ابھی تک نہیں سوئے تو شکریہ۔ محدود وقت کی وجہ سے مجھے بہت سے عنوانات پر مختصراً چھونا پڑا، لیکن مجھے امید ہے کہ گفتگو مفید رہی اور شاید حوصلہ افزا بھی۔
بٹ میپ اشاریہ جات کے بارے میں جاننا اچھا ہے، چاہے آپ کو ابھی ان کی ضرورت نہ ہو۔ انہیں اپنے ٹول باکس میں ایک اور ٹول بننے دیں۔
ہم نے گو کے لیے کارکردگی کی مختلف چالوں کو دیکھا ہے اور وہ چیزیں جن کو گو کمپائلر ابھی تک اچھی طرح سے نہیں سنبھالتا ہے۔ لیکن یہ جاننے کے لیے ہر گو پروگرامر کے لیے بالکل مفید ہے۔
میں آپ کو بس اتنا ہی بتانا چاہتا تھا۔ شکریہ!
ماخذ: www.habr.com