Files |  Tutorials |  Articles |  Links |  Home |  Team |  Forum |  Wiki |  Impressum

Aktuelle Zeit: Do Mär 28, 2024 10:19

Foren-Übersicht » Programmierung » Allgemein
Unbeantwortete Themen | Aktive Themen



Ein neues Thema erstellen Auf das Thema antworten  [ 2 Beiträge ] 
Autor Nachricht
 Betreff des Beitrags: SIMD Cachelines optimierung C++
BeitragVerfasst: Di Nov 10, 2015 19:00 
Offline
DGL Member
Benutzeravatar

Registriert: Di Mai 18, 2004 16:45
Beiträge: 2621
Wohnort: Berlin
Programmiersprache: Go, C/C++
Ich hab für meine HashList mit SIMD und Cacheline optimierung hantiert aber bisher mit mäßigen Erfolg.
Ist bei 5000 Elementen langsamer als normaler C++ Code aber skaliert mit steigender Elemente Zahl extrem gut.
Bei 50000 Elementen hab ich unter 10% mehr Cycles verbraucht, wo die C++ Code Variante dann sogar länger brauchte.

Code:
  1. RF_Type::Bool HashList::ContainsKey(const KeyType Key) const
  2. {
  3.     RF_Type::Bool result = false;
  4.     RF_Type::Size index = FindBucket(Key);
  5.     __m128i key0 = _mm_set1_epi32(Key);
  6.     __m128i key4 = _mm_load_si128(reinterpret_cast<const __m128i*>(&m_Keys[index]));
  7.  
  8.     key4 = _mm_cmpeq_epi32(key0, key4);
  9.     result = _mm_movemask_epi8(key4) != 0;
  10.     return result;
  11. }

Code:
  1. RF_Type::Bool HashList::ContainsKey(const KeyType Key) const
  2. {
  3.     RF_Type::Bool result = false;
  4.     RF_Type::Size index = Key & (m_Capacity-1);
  5.     for(RF_Type::Size i = 0; i < m_Capacity; ++i)
  6.     {
  7.         if(m_Keys[index] == m_EmptyKey)
  8.         {
  9.             break;
  10.         }
  11.         else
  12.         {
  13.             if(m_Keys[index] == Key)
  14.             {
  15.                 result = true;
  16.                 break;
  17.             }
  18.             index = (Key + i*i) & (m_Capacity - 1);
  19.         }
  20.     }
  21.     return result;
  22. }


Ich hab also Cacheline Utilization, Branching und Instruction based Sampling gemacht und hab raus bekommen, dass die Grundlast einfach zu hoch ist.
Wenn ich den SIMD Code verwende, dann explodiert im Debug Mode die Stackverwaltung.
Also beim Start der Funktion tut VC++ den Stack mit 0xDDDDDDDD auffüllen und dann die Variablen im Scope darauf mappen.
Das kostet durch die Größe der SIMD Variablen gut doppelt soviel Zeit und die holt der Code nicht mehr raus, also ist 2-4x langsamer.
Im Release gibt es dies natürlich nicht und da ist dann SIMD auch schneller als der C++ Code aber dennoch nicht zufriedendstellend.
Meine Instruktionsanzahl ist extrem gesunken ~30% aber ich verbrauche viel Zeit mit cache, speicherzugriff und das Pipelining wird nicht gut ausgenutzt, weil ich keine operationen hab, die ich einstreuen kann.

Ich bin leider auch nicht ganz SSE fest, was es der benutzung der richtigen Intrinsics betrifft.
Vieleicht hat wer noch eine Idee ? Ich bin aktuell Ratlos, wie ich das ganze noch effizienter hin bekomme, ohne die funktion komplett durch asm aus zu tauschen.

_________________
"Wer die Freiheit aufgibt um Sicherheit zu gewinnen, der wird am Ende beides verlieren"
Benjamin Franklin

Projekte: https://github.com/tak2004


Nach oben
 Profil  
Mit Zitat antworten  
 Betreff des Beitrags: Re: SIMD Cachelines optimierung C++
BeitragVerfasst: Mo Nov 16, 2015 20:53 
Offline
DGL Member
Benutzeravatar

Registriert: Di Mai 18, 2004 16:45
Beiträge: 2621
Wohnort: Berlin
Programmiersprache: Go, C/C++
Ich hab mich noch ein bisschen mit dem Thema beschäftigt und eine Finale Version, die zwar langsamer aber flexibler ist als die bisherige.
Code:
  1. RF_Type::Bool HashList::ContainsKey(const KeyType Key) const
  2. {
  3.     RF_Type::Size index = (Key & (m_BucketCount - 1))*m_BucketElements;
  4.     return RF_SysHardware::Vec128IntFindInt32(reinterpret_cast<const RF_Type::Vec128Int32*>(&m_Keys[index]), Key) != 0;
  5. }

Code:
  1. // X86 SSE2
  2. RF_Type::Int32 Vec128IntFindInt32(const RF_Type::Vec128Int32* Source, RF_Type::Int32 Value)
  3. {
  4.     __m128i a, b;
  5.     a = _mm_load_si128(reinterpret_cast<const __m128i*>(Source));
  6.     b = _mm_set1_epi32(Value);
  7.     a = _mm_cmpeq_epi32(a,b);
  8.     return _mm_movemask_epi8(a);
  9. }

Code:
  1. // ARM-NEON
  2. RF_Type::Int32 Vec128IntFindInt32(const RF_Type::Vec128Int32* Source, RF_Type::Int32 Value)
  3. {
  4.     int32x4_t a, b;
  5.     a = vld1q_s32(reinterpret_cast<const __m128i*>(Source));
  6.     b = vdupq_n_s32(Value);
  7.     a = vceqq_s32(a, b);
  8.     const int8_t __attribute__((aligned(16))) xr[8] = {-7, -6, -5, -4, -3, -2, -1, 0};
  9.     uint8x8_t mask_and = vdup_n_u8(0x80);
  10.     int8x8_t mask_shift = vld1_s8(xr);
  11.     uint8x8_t lo = vget_low_u8(a);
  12.     uint8x8_t hi = vget_high_u8(a);
  13.     lo = vand_u8(lo, mask_and);
  14.     lo = vshl_u8(lo, mask_shift);
  15.     hi = vand_u8(hi, mask_and);
  16.     hi = vshl_u8(hi, mask_shift);
  17.     lo = vpadd_u8(lo, lo);
  18.     lo = vpadd_u8(lo, lo);
  19.     lo = vpadd_u8(lo, lo);
  20.     hi = vpadd_u8(hi, hi);
  21.     hi = vpadd_u8(hi, hi);
  22.     hi = vpadd_u8(hi, hi);
  23.     return = ((hi[0] << 8) | (lo[0] & 0xFF));
  24. }

Ich hab den SIMD code wie üblich, in meinem Framework, hinter ein funktions dispatcher gepackt.
Der erlaubt mir zur Laufzeit auf die beste optimierung um zu schalten und kostet ein normalen funktionsaufruf, also kann nicht inlined werden, sowie der Stack baut sich auf und ab.
Genau das sind die kosten, die noch oben drauf gekommen sind aber die Vorteile waren einfach mehr Wert.
Durch den Dispatcher ist der Code wesentlich einfacher zu warten und strikt von systemabhängigen Code getrennt.

Ich hatte noch nach höheren Instruktionen geguckt, die es mit weniger Aufwand abfrühstücken aber nix gefunden.
Cachemässig hätte ich nur noch prefetch ausprobieren können aber schon in einem google treffer gelesen, dass das nix bringt, weil dazwischen keine weiteren Instruktionen liegen.

Ich hab ledeglich erfahren, dass ich meine lockfree Queue noch recht einfach optimieren kann aber das hatte hier mit nix zu tun.
Hier noch die nützliche Info.
Member Variablen sollte man prinzipiell zwischen lesen und schreiben aufteilen und zwischen diesen soviel Platz verbrauchen, dass die in unterschiedliche Cachelines kommen.
Was nun passiert ist, dass verschiedene Kerne sich nicht um die Cacheline prügeln, denn die müssen sonnst immer wieder aushandeln wer nun von beiden die Cacheline mit schreibzugriff bekommt und die anderen müssen die immer wieder synchronisieren, damit die nicht auf alte Daten arbeiten.
Bei C++ gibt es den modifier violate, welcher sagt, dass der cache garnicht benutzt werden soll und man direkt auf dem Speicherwert arbeitet, die bessere Alternative ist genau diese Technik.
Alle Threads die nur lesen wollen, bekommen eine andere Cacheline und werden nicht in den Kampf für die schreib Cacheline gezogen und sind somit viel schneller.
Das Beispiel war eine Lockfree Queue, die zur Kommunikation zwischen Threads benutzt wird, die hatte ne Payload von 16Byte und wurde mit 112Byte ungenutzten Datenmüll aufgefüllt, damit sie 128Byte und damit 2 Cachelines groß ist und ist damit wesentlich schneller.
Ist die Kommunikation nur einseitig, also alle Threads hämmern rein und ein einzelner Konsumiert hilft quasi kaum, da nur 1 Thread schneller wird.

_________________
"Wer die Freiheit aufgibt um Sicherheit zu gewinnen, der wird am Ende beides verlieren"
Benjamin Franklin

Projekte: https://github.com/tak2004


Nach oben
 Profil  
Mit Zitat antworten  
Beiträge der letzten Zeit anzeigen:  Sortiere nach  
Ein neues Thema erstellen Auf das Thema antworten  [ 2 Beiträge ] 
Foren-Übersicht » Programmierung » Allgemein


Wer ist online?

Mitglieder in diesem Forum: 0 Mitglieder und 33 Gäste


Du darfst keine neuen Themen in diesem Forum erstellen.
Du darfst keine Antworten zu Themen in diesem Forum erstellen.
Du darfst deine Beiträge in diesem Forum nicht ändern.
Du darfst deine Beiträge in diesem Forum nicht löschen.
Du darfst keine Dateianhänge in diesem Forum erstellen.

Suche nach:
Gehe zu:  
cron
  Powered by phpBB® Forum Software © phpBB Group
Deutsche Übersetzung durch phpBB.de
[ Time : 0.059s | 17 Queries | GZIP : On ]