إنتل x86 الجمعية تقنيات التحسين في عينة المشكلة
https://stackoverflow.com/questions/1414911
-
06-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russianسؤال
أنا أتعلم المجمع الكثير من الوقت وأنا أحاول كتابة بعض الإجراءات البسيطة \ وظائف لمعرفة مزايا الأداء (إن وجدت).بلدي الرئيسية تطوير أداة دلفي 2007 و الأمثلة الأولى سوف تكون في تلك اللغة ولكن يمكن ترجمتها بسهولة إلى لغات أخرى أيضا.
مشكلة الدول:
لأننا قدمنا غير موقعة قيمة البايت في كل من الثمانية بت يمثل بكسل في صف واحد من الشاشة.كل بكسل واحد يمكن أن تكون صلبة (1) أو شفافة (0).لذلك وبعبارة أخرى ، لدينا 8 بكسل معبأة في واحد بايت القيمة.أريد أن فك تلك بكسل في ثمانية صفيف بايت في الطريقة التي أصغر بكسل(بت) الأرض تحت أدنى مؤشر مجموعة وهلم جرا.هنا مثال:
One byte value -----------> eight byte array
10011011 -----------------> [1][1][0][1][1][0][0][1]
Array index number -------> 0 1 2 3 4 5 6 7
أدناه أقدم الأساليب الخمسة التي حل المشكلة.التالي سوف تظهر المقارنة الوقت و كيف فعلت قياس تلك الأوقات.
أسئلتي تتكون من جزأين:
1.
أنا أطلب منك مفصلة الجواب بشأن أساليب DecodePixels4a و DecodePixels4b.لماذا طريقة 4b ما هو أبطأ من 4a?
على سبيل المثال إذا كان ذلك أبطأ لأن قانون بلدي لا محاذاة بشكل صحيح ثم تظهر لي أي تعليمات في الأسلوب يمكن أن يكون أفضل الانحياز كيفية القيام بذلك لعدم كسر الأسلوب.
وأود أن نرى أمثلة حقيقية وراء نظرية.يرجى أن نضع في اعتبارنا أن أنا أتعلم الجمعية و أريد أن اكتساب المعرفة من إجاباتك الذي يسمح لي في المستقبل أن الكتابة أفضل رمز الأمثل.
2.
يمكنك الكتابة بشكل أسرع من الروتين DecodePixels4a?إذا كان الأمر كذلك, يرجى القرار الأمثل لوصف الخطوات التي عليك اتخاذها.قبل أسرع الروتين أعني الروتين الذي يعمل في أقصر فترة من الوقت في بيئة اختبار بين جميع إجراءات المقدمة هنا.
جميع معالجات إنتل الأسرة المسموح بها وتلك التي تتوافق معهم.
أدناه سوف تجد الروتين مكتوب لي من قبل:
procedure DecodePixels1(EncPixels: Byte; var DecPixels: TDecodedPixels);
var
i3: Integer;
begin
DecPixels[0] := EncPixels and $01;
for i3 := 1 to 7 do
begin
EncPixels := EncPixels shr 1;
DecPixels[i3] := EncPixels and $01;
//DecPixels[i3] := (EncPixels shr i3) and $01; //this is even slower if you replace above 2 lines with it
end;
end;
//Lets unroll the loop and see if it will be faster.
procedure DecodePixels2(EncPixels: Byte; var DecPixels: TDecodedPixels);
begin
DecPixels[0] := EncPixels and $01;
EncPixels := EncPixels shr 1;
DecPixels[1] := EncPixels and $01;
EncPixels := EncPixels shr 1;
DecPixels[2] := EncPixels and $01;
EncPixels := EncPixels shr 1;
DecPixels[3] := EncPixels and $01;
EncPixels := EncPixels shr 1;
DecPixels[4] := EncPixels and $01;
EncPixels := EncPixels shr 1;
DecPixels[5] := EncPixels and $01;
EncPixels := EncPixels shr 1;
DecPixels[6] := EncPixels and $01;
EncPixels := EncPixels shr 1;
DecPixels[7] := EncPixels and $01;
end;
procedure DecodePixels3(EncPixels: Byte; var DecPixels: TDecodedPixels);
begin
asm
push eax;
push ebx;
push ecx;
mov bl, al;
and bl, $01;
mov [edx], bl;
mov ecx, $00;
@@Decode:
inc ecx;
shr al, $01;
mov bl, al;
and bl, $01;
mov [edx + ecx], bl;
cmp ecx, $07;
jnz @@Decode;
pop ecx;
pop ebx;
pop eax;
end;
end;
//Unrolled assembly loop
procedure DecodePixels4a(EncPixels: Byte; var DecPixels: TDecodedPixels);
begin
asm
push eax;
push ebx;
mov bl, al;
and bl, $01;
mov [edx], bl;
shr al, $01;
mov bl, al;
and bl, $01;
mov [edx + $01], bl;
shr al, $01;
mov bl, al;
and bl, $01;
mov [edx + $02], bl;
shr al, $01;
mov bl, al;
and bl, $01;
mov [edx + $03], bl;
shr al, $01;
mov bl, al;
and bl, $01;
mov [edx + $04], bl;
shr al, $01;
mov bl, al;
and bl, $01;
mov [edx + $05], bl;
shr al, $01;
mov bl, al;
and bl, $01;
mov [edx + $06], bl;
shr al, $01;
mov bl, al;
and bl, $01;
mov [edx + $07], bl;
pop ebx;
pop eax;
end;
end;
// it differs compared to 4a only in switching two instructions (but seven times)
procedure DecodePixels4b(EncPixels: Byte; var DecPixels: TDecodedPixels);
begin
asm
push eax;
push ebx;
mov bl, al;
and bl, $01;
shr al, $01; //
mov [edx], bl; //
mov bl, al;
and bl, $01;
shr al, $01; //
mov [edx + $01], bl; //
mov bl, al;
and bl, $01;
shr al, $01; //
mov [edx + $02], bl; //
mov bl, al;
and bl, $01;
shr al, $01; //
mov [edx + $03], bl; //
mov bl, al;
and bl, $01;
shr al, $01; //
mov [edx + $04], bl; //
mov bl, al;
and bl, $01;
shr al, $01; //
mov [edx + $05], bl; //
mov bl, al;
and bl, $01;
shr al, $01; //
mov [edx + $06], bl; //
mov bl, al;
and bl, $01;
mov [edx + $07], bl;
pop ebx;
pop eax;
end;
end;
وهنا هو كيف يمكنني اختبار لهم:
program Test;
{$APPTYPE CONSOLE}
uses
SysUtils, Windows;
type
TDecodedPixels = array[0..7] of Byte;
var
Pixels: TDecodedPixels;
Freq, TimeStart, TimeEnd :Int64;
Time1, Time2, Time3, Time4a, Time4b: Extended;
i, i2: Integer;
begin
if QueryPerformanceFrequency(Freq) then
begin
for i2 := 1 to 100 do
begin
QueryPerformanceCounter(TimeStart);
for i := 1 to 100000 do
DecodePixels1(155, Pixels);
QueryPerformanceCounter(TimeEnd);
Time1 := Time1 + ((TimeEnd - TimeStart) / Freq * 1000);
QueryPerformanceCounter(TimeStart);
for i := 1 to 100000 do
DecodePixels2(155, Pixels);
QueryPerformanceCounter(TimeEnd);
Time2 := Time2 + ((TimeEnd - TimeStart) / Freq * 1000);
QueryPerformanceCounter(TimeStart);
for i := 1 to 100000 do
DecodePixels3(155, Pixels);
QueryPerformanceCounter(TimeEnd);
Time3 := Time3 + ((TimeEnd - TimeStart) / Freq * 1000);
QueryPerformanceCounter(TimeStart);
for i := 1 to 100000 do
DecodePixels4a(155, Pixels);
QueryPerformanceCounter(TimeEnd);
Time4a := Time4a + ((TimeEnd - TimeStart) / Freq * 1000);
QueryPerformanceCounter(TimeStart);
for i := 1 to 100000 do
DecodePixels4b(155, Pixels);
QueryPerformanceCounter(TimeEnd);
Time4b := Time4b + ((TimeEnd - TimeStart) / Freq * 1000);
end;
Writeln('Time1 : ' + FloatToStr(Time1 / 100) + ' ms. <- Delphi loop.');
Writeln('Time2 : ' + FloatToStr(Time2 / 100) + ' ms. <- Delphi unrolled loop.');
Writeln('Time3 : ' + FloatToStr(Time3/ 100) + ' ms. <- BASM loop.');
Writeln('Time4a : ' + FloatToStr(Time4a / 100) + ' ms. <- BASM unrolled loop.');
Writeln('Time4b : ' + FloatToStr(Time4b / 100) + ' ms. <- BASM unrolled loop instruction switch.');
end;
Readln;
end.
وهنا النتائج من الجهاز الخاص بي ( Intel® Pentium® E2180 على Win32 XP) :
Time1 : 1,68443549919493 ms. <- Delphi loop.
Time2 : 1,33773024572211 ms. <- Delphi unrolled loop.
Time3 : 1,37015271374424 ms. <- BASM loop.
Time4a : 0,822916962526627 ms. <- BASM unrolled loop.
Time4b : 0,862914462301607 ms. <- BASM unrolled loop instruction switch.
النتائج هي مستقرة جدا - تختلف مرات فقط قبل قليل في المئة بين كل اختبار صنعت.وكان ذلك صحيحا دائما: Time1 > Time3 > Time 2 > Time4b > Time4a
لذلك أعتقد أن دي الفرق بين Time4a و Time4b يعتمد من أن تعليمات التبديل في طريقة DecodePixels4b.في بعض الأحيان 4% في بعض الأحيان أنها تصل إلى 10% ولكن 4b دائما أبطأ من 4a.
كنت أفكر في طريقة أخرى مع استخدام MMX تعليمات الكتابة في الذاكرة ثمانية بايت في وقت واحد, ولكن أنا لا يمكن معرفة طريقة سريعة لفك بايت إلى 64 بت من التسجيل.
شكرا لك على وقتك.
شكرا يا رفاق لمداخلاتكم القيمة.انطلق أستطيع الرد على كل منكم في نفس الوقت ، للأسف مقارنة الحديثة وحدة المعالجة المركزية لدي واحد فقط "أنابيب" و يمكن تنفيذ واحدة فقط التعليمات "الرد" في ذلك الوقت؛ -) لذلك سأحاول تلخيص بعض الأمور هنا و كتابة تعليقات إضافية تحت إجاباتك.
أولا وقبل كل شيء أود أن أقول أنه قبل نشر سؤالي لقد جاء مع الحل الذي قدمه فوتر فان Nifterick وكان في الواقع الطريقة أبطأ ثم رمز التجميع.لذا قررت عدم نشر هذا الروتين هنا, ولكن قد ترى أن أخذت نفس النهج أيضا في حلقة دلفي نسخة من الروتين.فمن علق هناك لأنه كان يعاملني أسوأ النتائج.
هذا هو لغزا بالنسبة لي.لقد تشغيل التعليمات البرمجية مرة أخرى مع فوتر و فيلس هو الروتين وهنا النتائج:
Time1 : 1,66535493194387 ms. <- Delphi loop.
Time2 : 1,29115785420688 ms. <- Delphi unrolled loop.
Time3 : 1,33716934524107 ms. <- BASM loop.
Time4a : 0,795041753757838 ms. <- BASM unrolled loop.
Time4b : 0,843520166815013 ms. <- BASM unrolled loop instruction switch.
Time5 : 1,49457681191307 ms. <- Wouter van Nifterick, Delphi unrolled
Time6 : 0,400587402866258 ms. <- PhiS, table lookup Delphi
Time7 : 0,325472442519827 ms. <- PhiS, table lookup Delphi inline
Time8 : 0,37350491544239 ms. <- PhiS, table lookup BASM
نظرة على Time5 نتيجة, غريب جدا أليس كذلك ؟ أعتقد مختلفة دلفي نسخة منذ إنشاء الجمعية رمز يختلف عن تلك التي تقدمها فوتر.
الرئيسية الثانية تحرير:
أنا أعرف لماذا الروتين 5 كان أبطأ على machnie.وقد راجعت "مجموعة التدقيق" و "تجاوز التدقيق" في خيارات برنامج التحويل البرمجي.لقد تم إضافة assembler التوجيه إلى روتين 9 لمعرفة إذا كان ذلك يساعد.يبدو أن هذا التوجيه الجمعية الإجراء هو جيدة مثل دلفي مضمنة البديل أو حتى أفضل قليلا.
وهنا النتائج النهائية:
Time1 : 1,22508325749317 ms. <- Delphi loop.
Time2 : 1,33004145373084 ms. <- Delphi unrolled loop.
Time3 : 1,1473583622526 ms. <- BASM loop.
Time4a : 0,77322594033463 ms. <- BASM unrolled loop.
Time4b : 0,846033593023372 ms. <- BASM unrolled loop instruction switch.
Time5 : 0,688689382044384 ms. <- Wouter van Nifterick, Delphi unrolled
Time6 : 0,503233741036693 ms. <- PhiS, table lookup Delphi
Time7 : 0,385254722925063 ms. <- PhiS, table lookup Delphi inline
Time8 : 0,432993919452751 ms. <- PhiS, table lookup BASM
Time9 : 0,362680491244212 ms. <- PhiS, table lookup BASM with assembler directive
الرئيسية الثالثة تحرير:
في رأي @باسكال Cuoq و @j_random_hacker الفرق في تنفيذ مرات بين الروتين 4a, 4b و 5 بسبب الاعتماد على البيانات.ومع ذلك قد نختلف مع هذا الرأي مستندة على مزيد من الاختبارات التي أخرجتها.
لقد اخترع أيضا روتين جديد 4c على أساس 4a.هنا هو:
procedure DecodePixels4c(EncPixels: Byte; var DecPixels: TDecodedPixels);
begin
asm
push ebx;
mov bl, al;
and bl, 1;
mov [edx], bl;
mov bl, al;
shr bl, 1;
and bl, 1;
mov [edx + $01], bl;
mov bl, al;
shr bl, 2;
and bl, 1;
mov [edx + $02], bl;
mov bl, al;
shr bl, 3;
and bl, 1;
mov [edx + $03], bl;
mov bl, al;
shr bl, 4;
and bl, 1;
mov [edx + $04], bl;
mov bl, al;
shr bl, 5;
and bl, 1;
mov [edx + $05], bl;
mov bl, al;
shr bl, 6;
and bl, 1;
mov [edx + $06], bl;
shr al, 7;
and al, 1;
mov [edx + $07], al;
pop ebx;
end;
end;
أود أن أقول أنه هو جدا يعتمد على البيانات.
وها هي الاختبارات والنتائج.لقد قدمت أربعة اختبارات للتأكد من وجود أي حادث.لقد أضاف أيضا مرة جديدة بالنسبة للإجراءات المقترحة من قبل GJ (Time10a, Time10b).
Test1 Test2 Test3 Test4
Time1 : 1,211 1,210 1,220 1,213
Time2 : 1,280 1,258 1,253 1,332
Time3 : 1,129 1,138 1,130 1,160
Time4a : 0,690 0,682 0,617 0,635
Time4b : 0,707 0,698 0,706 0,659
Time4c : 0,679 0,685 0,626 0,625
Time5 : 0,715 0,682 0,686 0,679
Time6 : 0,490 0,485 0,522 0,514
Time7 : 0,323 0,333 0,336 0,318
Time8 : 0,407 0,403 0,373 0,354
Time9 : 0,352 0,378 0,355 0,355
Time10a : 1,823 1,812 1,807 1,813
Time10b : 1,113 1,120 1,115 1,118
Time10c : 0,652 0,630 0,653 0,633
Time10d : 0,156 0,155 0,172 0,160 <-- current winner!
كما قد نرى نتائج 4a, 4b, 4c و 5 هي قريبة جدا من بعضها البعض.لماذا هذا ؟ لأنني كنت إزالة من 4a, 4b (4c بالفعل لا يكون ذلك) اثنين تعليمات: push eax و pop eax.منذ وأنا أعلم أنني لن تستخدم في أي مكان آخر في بلدي رمز القيمة تحت eax لا يجب أن prereserve ذلك.الآن بلدي رمز زوج واحد فقط من دفع/البوب حتى الروتين 5.روتين 5 prereserves قيمة eax خدمة الزبائن beacause عليه أولا تقديم نسخة من تحت ecx ولكن deson لا prereserve ecx.
حتى استنتاجي هو أن:الفرق في وقت التنفيذ من 5 4a 4b (قبل الثالثة تحرير) لم القلق البيانات dependecny ولكن كان سببها إضافية الزوج من دفع / البوب تعليمات.
أنا مهتم جدا في التعليقات الخاصة بك.
بعد بضعة أيام GJ اخترع حتى أسرع الروتينية (الوقت 10d) من PhiS هو.عمل جميل GJ!
المحلول
Asm رمز النسبية بطيئة بسبب استخدام كومة نهاية كتابة 8 مرات إلى الذاكرة.تحقق هذا واحد...
procedure DecodePixels(EncPixels: Byte; var DecPixels: TDecodedPixels);
asm
xor ecx, ecx
add al, al
rcl ecx, 8
add al, al
rcl ecx, 8
add al, al
rcl ecx, 8
add al, al
rcl ecx, 1
mov [DecPixels + 4], ecx
xor ecx, ecx
add al, al
rcl ecx, 8
add al, al
rcl ecx, 8
add al, al
rcl ecx, 8
add al, al
rcl ecx, 1
mov [DecPixels], ecx
end;
ربما أسرع من كود مع جدول البحث!
نسخة محسنة:
procedure DecodePixelsI(EncPixels: Byte; var DecPixels: TDecodedPixels);
asm
mov ecx, 0 //Faster than: xor ecx, ecx
add al, al
rcl ch, 1
add al, al
rcl cl, 1
ror ecx, 16
add al, al
rcl ch, 1
add al, al
rcl cl, 1
mov [DecPixels + 4], ecx
mov ecx, 0 //Faster than: xor ecx, ecx
add al, al
rcl ch, 1
add al, al
rcl cl, 1
ror ecx, 16
add al, al
rcl ch, 1
add al, al
rcl cl, 1
mov [DecPixels], ecx
end;
الإصدار 3:
procedure DecodePixelsX(EncPixels: Byte; var DecPixels: TDecodedPixels);
asm
add al, al
setc byte ptr[DecPixels + 7]
add al, al
setc byte ptr[DecPixels + 6]
add al, al
setc byte ptr[DecPixels + 5]
add al, al
setc byte ptr[DecPixels + 4]
add al, al
setc byte ptr[DecPixels + 3]
add al, al
setc byte ptr[DecPixels + 2]
add al, al
setc byte ptr[DecPixels + 1]
setnz byte ptr[DecPixels]
end;
الإصدار 4:
const Uint32DecPix : array [0..15] of cardinal = (
$00000000, $00000001, $00000100, $00000101,
$00010000, $00010001, $00010100, $00010101,
$01000000, $01000001, $01000100, $01000101,
$01010000, $01010001, $01010100, $01010101
);
procedure DecodePixelsY(EncPixels: byte; var DecPixels: TDecodedPixels); inline;
begin
pcardinal(@DecPixels)^ := Uint32DecPix[EncPixels and $0F];
pcardinal(cardinal(@DecPixels) + 4)^ := Uint32DecPix[(EncPixels and $F0) shr 4];
end;
نصائح أخرى
في عام ، كنت شخصيا الابتعاد عن محاولة تحسين التعليمات البرمجية باستخدام الحيل على المجمع المستوى ، إلا إذا كنت حقا بحاجة إلى المزيد 2 أو 3% من السرعة ، وكنت على استعداد لدفع السعر من التعليمات البرمجية التي من الصعب قراءة ، والحفاظ على الميناء.
للضغط على الأخير 1%, قد يكون لديك حتى للحفاظ على عدة إصدارات الأمثل في المعالج, إذا أحدث معالجات محسنة باسكال يأتي على طول ، لن تستفيد من ذلك.
هذا دلفي رمز أسرع من أسرع المجمع كود:
procedure DecodePixels5(EncPixels: Byte; var DecPixels: TDecodedPixels);
begin
DecPixels[0] := (EncPixels shr 0) and $01;
DecPixels[1] := (EncPixels shr 1) and $01;
DecPixels[2] := (EncPixels shr 2) and $01;
DecPixels[3] := (EncPixels shr 3) and $01;
DecPixels[4] := (EncPixels shr 4) and $01;
DecPixels[5] := (EncPixels shr 5) and $01;
DecPixels[6] := (EncPixels shr 6) and $01;
DecPixels[7] := (EncPixels shr 7) and $01;
end;
Results:
Time1 : 1,03096806151283 ms. <- Delphi loop.
Time2 : 0,740308641141395 ms. <- Delphi unrolled loop.
Time3 : 0,996602425688886 ms. <- BASM loop.
Time4a : 0,608267951561275 ms. <- BASM unrolled loop.
Time4b : 0,574162510648039 ms. <- BASM unrolled loop instruction switch.
Time5 : 0,499628206138524 ms. !!! <- Delphi unrolled loop 5.
انها سريعة لأن العمليات يمكن القيام به مع السجلات فقط بدلا من الحاجة إلى تخزين وجلب الذاكرة.المعالجات الحديثة تنفيذ هذا جزئيا في موازاة ذلك (عملية جديدة يمكن أن تبدأ قبل السابق انتهى) ، لأن نتائج متتالية تعليمات مستقلة عن بعضها البعض.
رمز الجهاز يبدو مثل هذا:
push ebx;
// DecPixels[0] := (EncPixels shr 0) and 1;
movzx ecx,al
mov ebx,ecx
// shr ebx,$00
and bl,$01
mov [edx],bl
// DecPixels[1] := (EncPixels shr 1) and 1;
mov ebx,ecx
shr ebx,1
and bl,$01
mov [edx+$01],bl
// DecPixels[2] := (EncPixels shr 2) and 1;
mov ebx,ecx
shr ebx,$02
and bl,$01
mov [edx+$02],bl
// DecPixels[3] := (EncPixels shr 3) and 1;
mov ebx,ecx
shr ebx,$03
and bl,$01
mov [edx+$03],bl
// DecPixels[4] := (EncPixels shr 4) and 1;
mov ebx,ecx
shr ebx,$04
and bl,$01
mov [edx+$04],bl
// DecPixels[5] := (EncPixels shr 5) and 1;
mov ebx,ecx
shr ebx,$05
and bl,$01
mov [edx+$05],bl
// DecPixels[6] := (EncPixels shr 6) and 1;
mov ebx,ecx
shr ebx,$06
and bl,$01
mov [edx+$06],bl
// DecPixels[7] := (EncPixels shr 7) and 1;
shr ecx,$07
and cl,$01
mov [edx+$07],cl
pop ebx;
تحرير:كما اقترح طاولة البحث هو في الواقع أسرع.
var
PixelLookup:Array[byte] of TDecodedPixels;
// You could precalculate, but the performance gain would hardly be worth it because you call this once only.
for I := 0 to 255 do
DecodePixels5b(I, PixelLookup[I]);
procedure DecodePixels7(EncPixels: Byte; var DecPixels: TDecodedPixels);
begin
DecPixels := PixelLookup[EncPixels];
end;
Results:
Time1 : 1,03096806151283 ms. <- Delphi loop.
Time2 : 0,740308641141395 ms. <- Delphi unrolled loop.
Time3 : 0,996602425688886 ms. <- BASM loop.
Time4a : 0,608267951561275 ms. <- BASM unrolled loop.
Time4b : 0,574162510648039 ms. <- BASM unrolled loop instruction switch.
Time5 : 0,499628206138524 ms. !!! <- Delphi unrolled loop 5.
Time7 : 0,251533475182096 ms. <- simple table lookup
التوسع في نيك D الجواب ، حاولت الجدول التالي-بحث الإصدارات التي تستند ، والتي هي أسرع من تطبيقات تعطي (و أسرع من فوتر فان Nifterick رمز).
نظرا التالية معبأة مجموعة:
const Uint64DecPix : PACKED ARRAY [0..255] OF UINT64 =
( $0000000000000000, $0000000000000001, $0000000000000100, $0000000000000101, $0000000000010000, $0000000000010001, $0000000000010100, $0000000000010101, $0000000001000000, $0000000001000001, $0000000001000100, $0000000001000101, $0000000001010000, $0000000001010001, $0000000001010100, $0000000001010101,
$0000000100000000, $0000000100000001, $0000000100000100, $0000000100000101, $0000000100010000, $0000000100010001, $0000000100010100, $0000000100010101, $0000000101000000, $0000000101000001, $0000000101000100, $0000000101000101, $0000000101010000, $0000000101010001, $0000000101010100, $0000000101010101,
$0000010000000000, $0000010000000001, $0000010000000100, $0000010000000101, $0000010000010000, $0000010000010001, $0000010000010100, $0000010000010101, $0000010001000000, $0000010001000001, $0000010001000100, $0000010001000101, $0000010001010000, $0000010001010001, $0000010001010100, $0000010001010101,
$0000010100000000, $0000010100000001, $0000010100000100, $0000010100000101, $0000010100010000, $0000010100010001, $0000010100010100, $0000010100010101, $0000010101000000, $0000010101000001, $0000010101000100, $0000010101000101, $0000010101010000, $0000010101010001, $0000010101010100, $0000010101010101,
$0001000000000000, $0001000000000001, $0001000000000100, $0001000000000101, $0001000000010000, $0001000000010001, $0001000000010100, $0001000000010101, $0001000001000000, $0001000001000001, $0001000001000100, $0001000001000101, $0001000001010000, $0001000001010001, $0001000001010100, $0001000001010101,
$0001000100000000, $0001000100000001, $0001000100000100, $0001000100000101, $0001000100010000, $0001000100010001, $0001000100010100, $0001000100010101, $0001000101000000, $0001000101000001, $0001000101000100, $0001000101000101, $0001000101010000, $0001000101010001, $0001000101010100, $0001000101010101,
$0001010000000000, $0001010000000001, $0001010000000100, $0001010000000101, $0001010000010000, $0001010000010001, $0001010000010100, $0001010000010101, $0001010001000000, $0001010001000001, $0001010001000100, $0001010001000101, $0001010001010000, $0001010001010001, $0001010001010100, $0001010001010101,
$0001010100000000, $0001010100000001, $0001010100000100, $0001010100000101, $0001010100010000, $0001010100010001, $0001010100010100, $0001010100010101, $0001010101000000, $0001010101000001, $0001010101000100, $0001010101000101, $0001010101010000, $0001010101010001, $0001010101010100, $0001010101010101,
$0100000000000000, $0100000000000001, $0100000000000100, $0100000000000101, $0100000000010000, $0100000000010001, $0100000000010100, $0100000000010101, $0100000001000000, $0100000001000001, $0100000001000100, $0100000001000101, $0100000001010000, $0100000001010001, $0100000001010100, $0100000001010101,
$0100000100000000, $0100000100000001, $0100000100000100, $0100000100000101, $0100000100010000, $0100000100010001, $0100000100010100, $0100000100010101, $0100000101000000, $0100000101000001, $0100000101000100, $0100000101000101, $0100000101010000, $0100000101010001, $0100000101010100, $0100000101010101,
$0100010000000000, $0100010000000001, $0100010000000100, $0100010000000101, $0100010000010000, $0100010000010001, $0100010000010100, $0100010000010101, $0100010001000000, $0100010001000001, $0100010001000100, $0100010001000101, $0100010001010000, $0100010001010001, $0100010001010100, $0100010001010101,
$0100010100000000, $0100010100000001, $0100010100000100, $0100010100000101, $0100010100010000, $0100010100010001, $0100010100010100, $0100010100010101, $0100010101000000, $0100010101000001, $0100010101000100, $0100010101000101, $0100010101010000, $0100010101010001, $0100010101010100, $0100010101010101,
$0101000000000000, $0101000000000001, $0101000000000100, $0101000000000101, $0101000000010000, $0101000000010001, $0101000000010100, $0101000000010101, $0101000001000000, $0101000001000001, $0101000001000100, $0101000001000101, $0101000001010000, $0101000001010001, $0101000001010100, $0101000001010101,
$0101000100000000, $0101000100000001, $0101000100000100, $0101000100000101, $0101000100010000, $0101000100010001, $0101000100010100, $0101000100010101, $0101000101000000, $0101000101000001, $0101000101000100, $0101000101000101, $0101000101010000, $0101000101010001, $0101000101010100, $0101000101010101,
$0101010000000000, $0101010000000001, $0101010000000100, $0101010000000101, $0101010000010000, $0101010000010001, $0101010000010100, $0101010000010101, $0101010001000000, $0101010001000001, $0101010001000100, $0101010001000101, $0101010001010000, $0101010001010001, $0101010001010100, $0101010001010101,
$0101010100000000, $0101010100000001, $0101010100000100, $0101010100000101, $0101010100010000, $0101010100010001, $0101010100010100, $0101010100010101, $0101010101000000, $0101010101000001, $0101010101000100, $0101010101000101, $0101010101010000, $0101010101010001, $0101010101010100, $0101010101010101);
PUint64DecPix : pointer = @Uint64DecPix;
يمكنك كتابة التالي:
procedure DecodePixelsPS1Pas (EncPixels: Byte; var DecPixels: TDecodedPixels);
begin
DecPixels := TDecodedPixels(Uint64DecPix[EncPixels]);
end;
الإجراء DecodePixelsPS1PasInline (EncPixels:بايت;فار DecPixels:TDecodedPixels);مضمنة ؛ تبدأ
DecPixels := TDecodedPixels(Uint64DecPix[EncPixels]);الغاية ؛
الإجراء DecodePixelsPS1Asm (EncPixels:بايت;فار DecPixels:TDecodedPixels);asm
ليا ecx, Uint64DecPix //[<-إضافة في تحرير 3]
//mov ecx, dword ptr PUint64DecPix - بديل السطر أعلاه (أبطأ بالنسبة لي)
movzx eax ،
movq xmm0, [8*eax+ecx] //باستخدام XMM بدلا من MMX لذلك نحن لا يجب أن يصدر emm في النهاية
movq [edx], xmm0 //استخدام MOVQ لأنه لا حاجة mem المحاذاة
الغاية ؛
معيار PAS ASM تطبيقات متشابهة إلى حد ما سرعة الحكمة ، ولكن PAS التنفيذ مع وضع علامة "مضمن" هو أسرع لأنه يتخلص من كل مكالمة/ret تشارك في الدعوة الروتين.
- تحرير -:نسيت أن أقول:منذ كنت ضمنيا على افتراض شيئا عن تخطيط الذاكرة الخاصة بك TDecodedPixels هيكل ، فإنه سيكون من الأفضل إذا كنت تعلن أنها
PACKED ARRAY [0..7] of byte
--EDIT2--:هنا هي بلدي نتائج المقارنة:
Time1 : 2.51638266874701 ms. <- Delphi loop.
Time2 : 2.11277620479698 ms. <- Delphi unrolled loop.
Time3 : 2.21972066282167 ms. <- BASM loop.
Time4a : 1.34093090043567 ms. <- BASM unrolled loop.
Time4b : 1.52222070123437 ms. <- BASM unrolled loop instruction switch.
Time5 : 1.17106364076999 ms. <- Wouter van Nifterick
TimePS1 : 0.633099318488802 ms. <- PS.Pas
TimePS2 : 0.551617593856202 ms. <- PS.Pas Inline
TimePS3 : 0.70921094720139 ms. <- PS.Asm (speed for version before 3rd EDIT)
القائمون على القيام بعمل جيد جدا في تحسين إجراءات الصغيرة.
وأود أن تحسين التعليمات البرمجية الخاصة بك باستخدام جدول بحث.
منذ فك بايت واحد - 256 دول مختلفة - يمكنك precalculate 256 المصفوفات مع تفكيك القيم.
تحرير: علما أن معالجات Pentium يمكن تنفيذ تعليمات محددة بالتوازي (Superscalar العمارة) ، ويسمى الاقتران.
نقية البرمجيات الحل
باستخدام تقنية جميلة من هذا السؤال, الذي هو مرة أخرى مستوحاة من هذا السؤال سيكون لدينا حل كبير مثل هذا مع فقط سطر واحد من مدونة (باستثناء الإعلانات)
type TPackedDecodedPixels = record
case integer of
0: (a: TDecodedPixels);
1: (v: Int64);
end;
procedure DecodePixels(EncPixels: byte; var DecPixels: TDecodedPixels); inline;
const
magic = $8040201008040201;
mask = $8080808080808080;
begin
TPackedDecodedPixels(DecPixels).v := SwapEndian(((EncPixels*magic) and mask) shr 7);
end;
بالطبع كنت بحاجة للتأكد من أن DecPixels هو صحيح 8 بايت محاذاة أو قد تعاني من بعض إبطاء (أو حتى segfaults على أبنية).يمكنك أيضا بسهولة vectorize وظيفة لجعلها أسرع
التفسير:
نفترض لدينا ما يلي بت نمط abcdefgh.نريد إخراج مجموعة تحتوي على
0000000a 0000000b 0000000c 0000000d 0000000e 0000000f 0000000g 0000000h (1)
القراءة التي في little endian كما 64-بت عدد صحيح سوف تحصل على %0000000h0000000g0000000f0000000e0000000d0000000c0000000b0000000a.علينا أن نجد عددا السحر أن التحولات الأصلي بت المواقف التي يمكننا استخراج اللازمة بت
دعونا مضاعفة قيمة الرقم السحري
| b7 || b6 || b4 || b4 || b3 || b2 || b1 || b0 |
abcdefgh (1-byte value)
x 1000000001000000001000000001000000001000000001000000001000000001
__________________________________________________________________
= h0abcdefgh0abcdefgh0abcdefgh0abcdefgh0abcdefgh0abcdefgh0abcdefgh
في هذه المرحلة كل بكسل' بت تم نقلها إلى أهم أجزاء من المقابلة بايت.كما أنها كذبت في المكان المناسب, نحن بحاجة فقط إلى قطاع من البتات المتبقية مع and
| b7 || b6 || b4 || b4 || b3 || b2 || b1 || b0 |
h0abcdefgh0abcdefgh0abcdefgh0abcdefgh0abcdefgh0abcdefgh0abcdefgh
& 1000000010000000100000001000000010000000100000001000000010000000
__________________________________________________________________
= h0000000g0000000f0000000e0000000d0000000c0000000b0000000a0000000 (8-byte array)
الآن بكسل' بت في أهم أجزاء من المقابلة بايت, نحن بحاجة إلى القيام المنطقي الصحيح التحول من 7 لنقلها إلى الأقل أهمية الموقف.لأن المرجع يريد قيمة في عكس الترتيب ، نحن بحاجة SwapEndian() لتحويل وحدات البايت إلى big endian.إذا كنت ترغب فقط little endian يمكنك التوقف عند هذه الخطوة
ذلك الرقم السحري هو %1000000001000000001000000001000000001000000001000000001000000001 = $8040201008040201 و القناع %1000000010000000100000001000000010000000100000001000000010000000 = $8080808080808080.بالطبع في الواقع إلى حل المشكلة والحصول على تلك القيم ونحن بحاجة إلى القيام إلى الوراء من النتيجة النهائية → تضاعفت نتيجة → الرقم السحري
ولكن لماذا لم تضع بايت في little endian في (1) ثم أن تحويل إلى big endian?لماذا لا مجرد ترتيب وحدات البايت في endian كبيرة من أجل العثور على السحر لهذا الرقم ؟ في حال كنت أتساءل عن ذلك لأنه بهذه الطريقة سوف تعمل فقط في معظم 7 بت في المرة الواحدة.فعلت ذلك الطريق في بلادي القديمة الإجابة ويكون تقسيم قليلا ثم دمجها لاحقا
0abcdefg
x 0000000000000010000001000000100000010000001000000100000010000001
__________________________________________________________________
= 00000000abcdefgabcdefgabcdefgabcdefgabcdefgabcdefgabcdefgabcdefg
& 0000000000000001000000010000000100000001000000010000000100000001
__________________________________________________________________
= 000000000000000a0000000b0000000c0000000d0000000e0000000f0000000g
دعم الأجهزة
هذا هو في الواقع حالة خاصة من بت توسيع مع ثابت قناع.في AVX2 قدمت إنتل pdep التعليمات في BMI2 مجموعة التعليمات لهذا الغرض ، لذا تحتاج فقط تعليمة واحدة للحصول على النتيجة.في لغات أخرى يمكنك استخدام هذا مع جوهري وظيفة _pext_u64.للأسف AFAIK Free Pascal لا يعتمد عليه وكان لديك لاستخدام الجمعية مباشرة.ومع ذلك التعبير سوف تبدو مثل
TPackedDecodedPixels(DecPixels).v := _pext_u64(EncPixels, $0101010101010101);
صحة الاختيار:
حاولت مقارنة OP نسخة مع كل الإصدارات و لم أجد أي مشكلة حتى الآن.على مترجم الانتاج مثل هذا
mov al, dil
mov rbx, rsi
movzx edi, al
movabs rax, 0x8040201008040201
imul rdi, rax
movabs rax, 0x8080808080808080
and rdi, rax
shr rdi, 0x7
call 4016a0 <SYSTEM_$$_SWAPENDIAN$INT64$$INT64>
mov QWORD PTR [rbx], rax
الشركة العامة للفوسفات الانتاج لا يزال دون المستوى الأمثل لأن المترجم لا يعرف محل الدعوة إلى SwapEndian مع BSWAP, و نسخ البيانات دون داع.لماذا mov al, dil; movzx edi, al بدلا من مجرد movzx edi, dil?.كما يمكنك أن ترى, النواتج من C و C++ compilers هي أفضل بكثير
كنت على وشك أن تعطي نفس الخوارزمية كما فوتر فان Nifterick.
وبالإضافة إلى ذلك, وأود أن أشرح أداء أفضل من حيث التبعية سلاسل.في كل من الإصدارات التي اقترحت ، عند بسطه الأساسي حلقة كتمت التبعية بين اثنين من التكرارات المتعاقبة:كل shr al, $01;يتطلب القيمة السابقة من آل تم حسابها.إذا كنت تنظيم بسطه التكرار بحيث يمكن تنفيذها بالتوازي ، وسوف يكون في الواقع على المعالج الحديث.لا تنخدع كاذبة التبعيات التي يمكن قمعها من قبل السجل تسمية.
وأشار أحدهم إلى أنه بنتيوم يمكن تنفيذ التعليمات اثنين في وقت واحد.هذا صحيح ، لكن المعالجات الحديثة (منذ بنتيوم برو ، PII,...,Core, Core 2) يتم تنفيذ أكثر من اثنين التعليمات في نفس الوقت ، عندما يكون لديهم فرصة -- وهذا هو عندما لا يكون هناك تبعية بين التعليمات التي يجري تنفيذها.لاحظ كيف في فوتر فان Nifterick نسخة كل خط يمكن تنفيذها بشكل مستقل عن الآخرين.
http://www.agner.org/optimize/ لديه كل المعلومات التي يمكن أن تحتاج من أي وقت مضى إلى فهم بنية المعالجات الحديثة وكيفية الاستفادة منها.
إذا كنت فقط دعم 80386 أعلاه يمكنك استخدام BTcc و SETcc مجموعة من التعليمات في هذه الطريقة:
BT ax,1
SETC [dx]
inc dx
BT ax,2
SETC [dx]
inc dx
الخ
ماذا عن شيء مثل:
/* input byte in eax, address to store result in edx */
and eax, 0xff /* may not be needed */
mov ebx, eax
shl ebx, 7
or eax, ebx
mov ebx, eax
shl ebx, 14
or eax, ebx
mov ebx, eax
and eax, 0x01010101
mov [edx], eax
shr ebx, 4
and ebx, 0x01010101
mov [edx+4], ebx
السبب المرجح أن 4b أسرع من 4a هو أنه parallelizes أفضل.من 4a:
mov bl, al;
and bl, $01; // data dep (bl)
mov [edx], bl; // data dep (bl)
shr al, $01;
mov bl, al; // data dep (al)
and bl, $01; // data dep (bl)
mov [edx + $01], bl; // data dep (bl)
تعليمات وضع علامة "البيانات dep" لا يمكن أن تبدأ المنفذة حتى التعليم السابق قد انتهى ، و كتبت السجلات التي تسبب هذه البيانات التبعية.وحدات المعالجة المركزية الحديثة قادرة على بدء التعليم قبل الأخير اكتمال إذا كان هناك أي تبعية.ولكن الطريقة التي كنت قد أمرت هذه العمليات يمنع هذا.
في 4b, لديك عدد أقل من البيانات تبعيات:
mov bl, al;
and bl, $01; // data dep (bl)
shr al, $01;
mov [edx], bl;
mov bl, al;
and bl, $01; // data dep (bl)
shr al, $01;
mov [edx + $01], bl;
مع هذه التعليمات يأمر أقل من التعليمات تعتمد على تعليمات سابقة, حتى لا يكون هناك المزيد من الفرص للحصول على التوازي.
لا يمكنني أن أضمن أن هذا هو سبب اختلاف السرعة ، وإنما هو المرشح المحتمل.للأسف من الصعب أن تأتي عبر إجابات مطلقة مثل تلك التي كنت تبحث عن ؛ المعالجات الحديثة لديها فرع تنبئ متعدد المستويات مخابئ الأجهزة قبل fetchers ، وجميع أنواع أخرى من التعقيدات التي يمكن أن تجعل من الصعب عزل أسباب الاختلافات الأداء.أفضل ما يمكنك فعله هو قراءة الكثير ، إجراء التجارب والحصول على دراية أدوات أخذ جيدة القياسات.
أنا تخمين هو أن الكتابة إلى الذاكرة (في الواقع, ذاكرة التخزين المؤقت) أبطأ من العمل مع السجلات.
لذلك ،
mov [edx+...], bl
shr al, $01;
mov bl, al;
يعطي المعالج بعض الوقت لكتابة bl إلى الذاكرة قبل bl التسجيل مطلوب مرة أخرى ، في حين
shr al, $01;
mov [edx], bl;
mov bl, al;
يحتاج bl على الفور حتى المعالج إلى التوقف والانتظار ذاكرة الكتابة لإكمال.
هذا هو المستغرب بالنسبة لي.الحديث معالجات إنتل فعل مجنون pipelining و تسجيل تسمية لذلك في رأيي, إذا كان أي شيء ، DecodePixels4b ينبغي أن يكون أسرع ، منذ تبعيات كل التعليمات هي أبعد من ذلك.ما سبق هو شرح ما يمكن أن تقدمه ، وبصرف النظر عن هذا:
x86 فظيع مجموعة التعليمات ، إنتل هل مذهلة ومتقدمة جدا التهريج لجعلها فعالة.إذا كنت سوف ننظر إلى شيء آخر.هناك القليل جدا من الطلب على megaMcOptimised البرمجيات على أجهزة الكمبيوتر اليوم.بلدي ودية اقتراح هو أن ننظر إلى معالجات الأجهزة المحمولة (أساسا الذراع) ، لأن في الأجهزة المحمولة, سرعة المعالج, استهلاك الطاقة وعمر البطارية المخاوف يعني أن الصغرى الأمثل البرمجيات هو أكثر أهمية.والذراع لديه متفوقة مجموعة التعليمات إلى x86.
SIMD
إذا كنت تمديد خوارزمية معالجة المصفوفات ، ثم SIMD يصبح الخيار الأمثل.وهنا SIMD إصدار هذا 1/3 الوقت الأمثل ج أي ما يعادل:
int main ()
{
const int
size = 0x100000;
unsigned char
*source = new unsigned char [size],
*dest,
*dest1 = new unsigned char [size * 32],
*dest2 = new unsigned char [size * 32];
for (int i = 0 ; i < size ; ++i)
{
source [i] = rand () & 0xff;
}
LARGE_INTEGER
start,
middle,
end;
QueryPerformanceCounter (&start);
dest = dest1;
for (int i = 0 ; i < size ; ++i)
{
unsigned char
v = source [i];
for (int b = 0 ; b < 8 ; ++b)
{
*(dest++) = (v >> b) & 1;
}
}
unsigned char
bits [] = {1,2,4,8,16,32,64,128,1,2,4,8,16,32,64,128},
zero [] = {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
ones [] = {1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1};
QueryPerformanceCounter (&middle);
__asm
{
movdqu xmm1,bits
movdqu xmm2,zero
movdqu xmm3,ones
mov ecx,0x100000/4
mov esi,source
mov edi,dest2
l1:
lodsd
movd xmm0,eax
movd xmm4,eax
punpcklbw xmm0,xmm0
punpcklbw xmm4,xmm4
punpcklwd xmm0,xmm0
punpcklwd xmm4,xmm4
punpckldq xmm0,xmm0
punpckhdq xmm4,xmm4
pand xmm0,xmm1
pand xmm4,xmm1
pcmpeqb xmm0,xmm2
pcmpeqb xmm4,xmm2
paddb xmm0,xmm3
paddb xmm4,xmm3
movdqu [edi],xmm0
movdqu [edi+16],xmm4
add edi,32
dec ecx
jnz l1
}
QueryPerformanceCounter (&end);
cout << "Time taken = " << (middle.QuadPart - start.QuadPart) << endl;
cout << "Time taken = " << (end.QuadPart - middle.QuadPart) << endl;
cout << "memcmp = " << memcmp (dest1, dest2, size * 32) << endl;
return 0;
}
لا يصدق الحل الذكي كريس, ماذا ستفعل مع المشكلة العكسية:جعل بايت من مجموعة من 8 بايت?
غير الأمثل حل المشكل:
BtBld PROC Array:DWORD, Pixels:DWORD
mov eax, [Array]
add eax, 7
mov edx, [Pixels]
mov bx, 0
mov ecx, 8
rpt: or bx, [eax]
dec eax
shl bx, 1
loop rpt
shr bx, 1
mov [edx], bl
ret
BtBld ENDP
كما لاحظت الفرق من سرعة في 4a 4b التنفيذ بسبب وحدة المعالجة المركزية الأمثل (من خلال تنفيذ عدة تعليمات في موازاة / pipelining التعليمات).ولكن العامل ليس هو في المعاملات ، ولكن بسبب طبيعة المشغل نفسه.
4a Instruction Sequence:
AND - MOV - SHR
4b Instruction Sequence:
AND - SHR - MOV
كلا و SHR استخدام الأعلام تسجيل هذه التعليمات قد الانتظار في خط أنابيب.
قراءتها على النحو التالي:
4a: AND (piped) MOV (piped) SHR
4b: AND (WAIT) SHR (piped) MOV
الخلاصة:4b 7 المزيد من الانتظار الدولة في خط أنابيب من 4a, وبالتالي فمن أبطأ.
جوش ذكر أن هناك بيانات التبعيات ، أي:
mov bl, al;
and bl, $01; // data dep (bl)
ولكن هذا ليس صحيحا تماما لأن هذين التعليمات يمكن أن يكون جزئيا أعدم في paralel في مستوى وحدة المعالجة المركزية:
mov bl, al -> (A:) read al (B:) write bl => (2 clocks in i386)
and bl, 01 -> (C:) read 01 (D:) write bl => idem
بالتتابع أنها تأخذ 4 ساعات ، ولكن ضخه أنها تأخذ فقط 3 "الساعات" (في الواقع مصطلح "الساعة" ليست كافية في خط أنابيب المنظور ولكن كنت عليه في سياق البساطة)
[--A--][--B--]
[--C--]<wait>[---D--]
