اليوم سنعمل على تسريع ربط الخطوط القصيرة في Go بنسبة 30٪. ولهذا لن نحتاج إلى تعديل Go نفسها ، سيتم تنفيذ كل هذا كمكتبة خارجية .

تحت الخفض أنتظر:

• مقارنة بين strings.Builder + ، strings.Builder والتسلسل الأصلي
• اذهب إلى تفاصيل الصف الداخلي
• قليل من المجمع

يمكن اعتبار هذه المقالة أيضًا عذرًا لمناقشة CL123256: وقت التشغيل ، cmd / compile: تخصص concatstring2 . نرحب بأفكار تحسين قائمة التغيير هذه.

نتائج فورية

تمت المقارنة مع إصدار go tip (الرئيسي) للمترجم. يمكنك الحصول على نتائج مماثلة في الإصدارات حول Go 1.5. كان آخر تغيير مهم في دالة concatstrings هو CL3120: cmd / gc: تخصيص المخازن المؤقتة للسلاسل غير المنجزة على المكدس .

 BenchmarkConcat2Operator-8 20000000 83.8 ns/op BenchmarkConcat2Builder-8 20000000 70.9 ns/op BenchmarkConcat2-8 20000000 62.1 ns/op BenchmarkConcat3Operator-8 20000000 104 ns/op BenchmarkConcat3Builder-8 20000000 89.9 ns/op BenchmarkConcat3-8 20000000 82.1 ns/op 

يستخدم ConcatOperator + .
يستخدم ConcatBuilder المسبق الصحيح.
تستخدم Concat الوظيفة التي Concat كجزء من هذه القصة.

مقارنة عبر منصة الإحصاء :

 name old time/op new time/op delta Concat2-8 84.2ns ± 1% 62.7ns ± 2% -25.49% (p=0.000 n=9+10) Concat3-8 103ns ± 3% 83ns ± 4% -19.83% (p=0.000 n=10+9) 

تنفيذ المجمّع تحت GOARCH=AMD64 أسرع قليلاً ولديه تحسين إضافي ، وهو موجود في عامل التشغيل المدمج + ، ولكن أكثر على ذلك أدناه:

 name old time/op new time/op delta Concat2-8 84.2ns ± 1% 57.1ns ± 3% -32.20% (p=0.000 n=9+9) 

سنأخذ وظيفة المجمع كأداء 100٪ (بالنسبة إلى باقي التطبيقات المدروسة).

يمكن رؤية نتائج الخطوط الأطول في README.md . كلما كانت السلسلة أطول ، كلما قل الفرق بين عمليات التنفيذ.

تسلسل ساذج

الحل الأسهل هو استخدام عامل التشغيل + .

دلالات هذا البيان كما يلي: خذ سطرين وإرجاع سلسلة نتيجة تحتوي على سلسلة من كلا السطرين. ليس هناك ما يضمن عودة خط جديد. على سبيل المثال ، إذا كان هناك سلسلة من سلسلة فارغة وأي سلسلة أخرى ، فقد يعرض وقت التشغيل وسيطة غير فارغة ، وتجنب الحاجة إلى تخصيص ذاكرة جديدة ونسخ البيانات هناك.

ولكن ، كما يتبين من النتائج في بداية المقال ، فإن هذه هي أبطأ طريقة.

 func concat2operator(x, y string) string { return x + y } 

تقييم الأداء: 67.8٪ .

سلاسل باني

منذ وقت ليس ببعيد ، تمت إضافة نوع جديد إلى Go - strings.Builder . هذا تناظري bytes.Buffer ، ولكن عند استدعاء الأسلوب String() ، لا يتم إعادة تخصيص الذاكرة ولا يتم نسخ البيانات.

على عكس bytes.Buffer ، لا bytes.Buffer الباني bytes.Buffer مؤقت صغير ، وبالتالي ، تم تخصيص ذاكرة مسبقًا لسلسلة. إذا كنت لا تستخدم طريقة Grow ، فسيكون الأداء أسوأ من bytes.Buffer . تحدث العديد من الانحدارات في Go 1.11 بسبب هذه الميزة المحددة (انظر CL113235 ).

في الكود الخاص بنا ، من أجل نقاء التجربة ، سنتجنب هذا الخطأ.

 func concat2builder(x, y string) string { var builder strings.Builder builder.Grow(len(x) + len(y)) //      builder.WriteString(x) builder.WriteString(y) return builder.String() } 

تقييم الأداء: 80.5٪ (+ 12.7).

إنشاء رمز التسلسل

إذا نظرنا إلى الرمز الذي ينشئه المحول البرمجي لعامل التشغيل + ، concatstring2 مكالمات إلى وظائف concatstring3 و concatstring3 وما إلى ذلك (حتى concatstring5 ضمناً).

 func concat2codegen(x, y) string { return x + y } // => CALL runtime.concatstring2(SB) func concat3codegen(x, y, z) string { return x + y + z } // => CALL runtime.concatstring3(SB) 

ألق نظرة على runtime / string.go نفسها :

 func concatstring2(buf *tmpBuf, a [2]string) string { return concatstrings(buf, a[:]) } func concatstring3(buf *tmpBuf, a [3]string) string { return concatstrings(buf, a[:]) } 

لذا ، يبقى تعلم وظيفة concatstrings .
قائمة كاملة متاحة أدناه تحت المفسد ، ولكن هنا وصف عالي المستوى:

1. قد تكون المعلمة buf nil . يتم تخصيص هذا المخزن المؤقت من قبل المترجم إذا لم "يهرب" السطر من تعريفه. إذا كانت السلسلة تعيش لفترة أطول من الإطار ، فإن هذا المخزن المؤقت سيكون دائمًا nil (كما يحدث في أغلب الأحيان). ومع ذلك ، إذا كان هذا المخزن المؤقت متاحًا ، فسيكون من الممكن تجنب التخصيص في حالة اختراق النتيجة فيه (حجمه 32 بايت).
2. إذا كانت كافة الأسطر باستثناء سطر فارغ ، ستُرجع الدالة هذا السطر. ولكن في الوقت نفسه ، تتجاوز الخطوط المحددة على المكدس وتترك إطارها هذا التحسين بحيث لا يتلقى المتصل ذاكرة محررة بالفعل.
3. علاوة على ذلك ، يتم نسخ جميع الخطوط إلى الذاكرة الجديدة.

 // concatstrings implements a Go string concatenation x+y+z+... // The operands are passed in the slice a. // If buf != nil, the compiler has determined that the result does not // escape the calling function, so the string data can be stored in buf // if small enough. func concatstrings(buf *tmpBuf, a []string) string { idx := 0 l := 0 count := 0 for i, x := range a { n := len(x) if n == 0 { continue } if l+n < l { throw("string concatenation too long") } l += n count++ idx = i } if count == 0 { return "" } // If there is just one string and either it is not on the stack // or our result does not escape the calling frame (buf != nil), // then we can return that string directly. if count == 1 && (buf != nil || !stringDataOnStack(a[idx])) { return a[idx] } s, b := rawstringtmp(buf, l) for _, x := range a { copy(b, x) b = b[len(x):] } return s } 

نرى هنا عدة أماكن في آن واحد يمكن تحسينها لحالة معينة:

• buf معظم الأحيان فارغة. عندما لا يتمكن المترجم من إثبات أن السلسلة آمنة لوضعها على المكدس ، فإن تمرير معلمة إضافية والتحقق من nil وجود nil داخل الوظيفة يعطي فقط حملًا علويًا.
• للحالة الخاصة مع len(a) == 2 لا نحتاج إلى دورة ويمكن تبسيط الحسابات. وهذا هو الشكل الأكثر شيوعًا للتسلسل.

نسخة لجميع المعماريات

لتنفيذ التخصص ، نحتاج إلى معرفة كيفية تمثيل الخطوط في Go. التوافق الثنائي مهم بالنسبة لنا ، في حين أنه غير unsafe.Pointer استبدال unsafe.Pointer بـ *byte دون أي تضحيات.

 type stringStruct struct { str *byte len int } 

الاستنتاج الثاني المهم الذي يمكننا استخلاصه من وقت التشغيل: تبدأ الخطوط حياتهم قابلة للتغيير. يتم تخصيص جزء من الذاكرة يتم الرجوع إليه بواسطة []byte ، حيث تتم كتابة محتويات السطر الجديد ، وبعد ذلك فقط []byte تجاهل []byte ، ويتم تخزين الذاكرة التي تشير إليها في stringStruct .

بالنسبة لأولئك الذين يريدون المزيد من التفاصيل ، يقترح دراسة وظائف rawstringtmp و rawstring .

 // rawstring allocates storage for a new string. The returned // string and byte slice both refer to the same storage. // The storage is not zeroed. Callers should use // b to set the string contents and then drop b. func rawstring(size int) (s string, b []byte) { p := mallocgc(uintptr(size), nil, false) stringStructOf(&s).str = p stringStructOf(&s).len = size *(*slice)(unsafe.Pointer(&b)) = slice{p, size, size} return } 

يمكننا تحريك نفسها تقريبًا ، باستخدام الجانب المظلم من الحزمة unsafe :

 func concat2(x, y string) string { length := len(x) + len(y) if length == 0 { return "" } b := make([]byte, length) copy(b, x) copy(b[len(x):], y) return goString(&b[0], length) } 

نسلط الضوء على []byte ، والذي نستخدمه لتشكيل محتويات سطر جديد. ثم يمكننا إنهاء الخط فقط من خلال إحضاره إلى تمثيل وقت التشغيل المتوقع. وظيفة goString مسؤولة عن هذا:

 func goString(ptr *byte, length int) string { s := stringStruct{str: ptr, len: length} return *(*string)(unsafe.Pointer(&s)) } 

تقييم الأداء: 91.9٪ (+ 10.9).

إصدار AMD64

لسوء الحظ ، لا يحتوي الإصدار السابق من الوظيفة على تحسين للتسلسل بسلسلة فارغة ، ونقوم أيضًا بإجراء عدد من الحسابات غير الضرورية بسبب عدم القدرة على تخصيص الذاكرة مباشرة ، علينا العمل مع شريحة البايت.

إحدى الميزات المثيرة للاهتمام في أداة التجميع Go هي أنها تسمح لك بالاتصال ، على سبيل المثال ، بوظائف وقت التشغيل غير القابلة للتصدير. يمكننا استدعاء runtime·mallocgc من رمز التجميع حتى لو لم يكن جزءًا من حزمة runtime . سوف نستخدم هذه الخاصية.

يمكننا أيضًا التحقق من ملكية خطوط ذاكرة المكدس ، مما يجعلها آمنة لتحسين عودة إحدى الوسيطات نتيجة لذلك.

افترض أن دالة تم استدعاؤها باستخدام وسيطات concat2("", "123") . x عبارة عن سلسلة فارغة ، وإذا لم y تخصيص y على المكدس ، فيمكننا إرجاعها كنتيجة للتسلسل.

 //; ,  x  y   stringStruct. //; CX - y.str. //; SI - y.len. maybe_return_y: //;      . MOVQ (TLS), AX //; *g CMPQ CX, (AX) JL return_y //;  y_str < g.stack.lo CMPQ CX, 8(AX) JGE return_y //;  y_str >= g.stack.hi JMP concatenate //; y  ,    return_y: MOVQ CX, ret+32(FP) //; stringStruct.len MOVQ SI, ret+40(FP) //; stringStruct.str RET 

MOVQ (TLS), AX * g إلى سجل AX . القراءة عند الإزاحة الصفرية ستعطي حقل g.stack.lo ، ويبدأ g.stack.hi بالبايت الثامن (لمنصة 64 بت).

 type g struct { stack struct { lo uintptr // 0(AX) hi uintptr // 8(AX) } stackguard0 uintptr // 16(AX) stackguard1 uintptr // 24(AX) // ...   } 

يخصص الجسم concatenate الذاكرة ويملأها بكلا الخطين ويعيد سطرًا جديدًا.

 #include "textflag.h" #include "funcdata.h" TEXT ·Strings(SB), 0, $48-48 NO_LOCAL_POINTERS //    . MOVQ x+0(FP), DX MOVQ x+8(FP), DI MOVQ y+16(FP), CX MOVQ y+24(FP), SI TESTQ DI, DI JZ maybe_return_y // x -  ,   y TESTQ SI, SI JZ maybe_return_x // y -  ,   x concatenate: LEAQ (DI)(SI*1), R8 // len(x) + len(y) //     . MOVQ R8, 0(SP) MOVQ $0, 8(SP) MOVB $0, 16(SP) CALL runtime·mallocgc(SB) MOVQ 24(SP), AX //     MOVQ AX, newstr-8(SP) //  x. MOVQ x+0(FP), DX MOVQ x+8(FP), DI MOVQ AX, 0(SP) MOVQ DX, 8(SP) MOVQ DI, 16(SP) CALL runtime·memmove(SB) //  y   len(x). MOVQ x+8(FP), DI MOVQ y+16(FP), CX MOVQ y+24(FP), SI MOVQ newstr-8(SP), AX LEAQ (AX)(DI*1), BX MOVQ BX, 0(SP) MOVQ CX, 8(SP) MOVQ SI, 16(SP) CALL runtime·memmove(SB) //   . MOVQ newstr-8(SP), AX MOVQ x+8(FP), R8 ADDQ y+24(FP), R8 MOVQ AX, ret+32(FP) MOVQ R8, ret+40(FP) RET maybe_return_y: //      . MOVQ (TLS), AX // *g CMPQ CX, (AX) JL return_y //  y_ptr < stk.lo CMPQ CX, 8(AX) JGE return_y //  y_ptr >= stk.hi JMP concatenate // y  ,    return_y: MOVQ CX, ret+32(FP) MOVQ SI, ret+40(FP) RET maybe_return_x: //      . MOVQ (TLS), AX // *g CMPQ DX, (AX) JL return_x //  x_ptr < stk.lo CMPQ DX, 8(AX) JGE return_x //  x_ptr >= stk.hi JMP concatenate // x  ,    return_x: MOVQ DX, ret+32(FP) MOVQ DI, ret+40(FP) RET 

تقييم الأداء: 100٪ (+8.6).

في الختام

يتم توفير جميع التعليمات البرمجية كحزمة concat .

هل العالم جاهز لمثل هذا التسلسل السريع؟ من يدري.

في بداية المقال ، تم ذكر CL123256 . لديه العديد من مسارات التطوير:

1. التخصص المتغير للحالة عندما لا يقوم المحول البرمجي بتخصيص مخزن مؤقت. هناك نمو أقل لكل حالة ، ولكنه يغطي المزيد من أنواع التسلسل ولا يزيد عمليًا من حجم الشفرة (كل من الجهاز ورمز Go).
2. المزيد من التخصصات للحالات الخاصة. يمكن أن تؤذي المكاسب الأعلى ، ولكن المزيد من كود الآلة ، ذاكرة التخزين المؤقت للإرشادات.
3. طن من كود الآلة ، لكل حالة خاصة ومذكرة متخصصة ، بطريقة كيفية القيام بذلك في glibc. هنا تنشأ بشكل رئيسي أسئلة النفعية.

يسرع الخيار المقترح الحالي فقط الحالة الأكثر شيوعًا وأبسطًا لسلسلة من السلاسل (arity = 2).

إذا لم يقبل Go هذا التغيير ، فيمكن تحقيق تسارع مماثل من خلال تنفيذ عمليات السلسلة في شكل مكتبة خارجية. أقل ملاءمة وجميلة وأنيقة ، لكنها تعمل.