Main place for discussions about U++ cross platform development framework.
SSE2 and SVO optimization (Painter, memcpy....)
Hi, Here's an optimization for BufferPainter. BufferPainter::Clear(RGBA) speed is improved by over 30 % with the following change in Painter/Render.cpp: void BufferPainter::ClearOp(const RGBA& color) { // UPP::Fill(~*ip, color, ip->GetLength()); FillRGBA(~*ip, color, ip->GetLength()); ip->SetKind(color.a == 255 ? IMAGE_OPAQUE : IMAGE_ALPHA); } And in Painter/Fillers.h: namespace Upp { // Add the following line: #define FillRGBA(a,b,c) memsetd((a),*(dword*)&(b),(c)) struct SolidFiller : Rasterizer::Filler { This may be significant in some usage scenarios as it can currently take e.g. 4.5 milliseconds to clear a 4K ImageBuffer before drawing to it. This can now be reduced to 2.8 milliseconds. Best regards, Tom EDIT: Changed code to use the newly optimized FillRGBA() found in Fillers.h. This can be found at: https://www.ultimatepp.org/forums/index.php?t=msg&th=110 11&goto=53752&#msg_53752
Tom1 wrote on Mon, 27 April 2020 19:19 Hi, Here's an optimization for BufferPainter. BufferPainter::Clear(RGBA) speed is improved by over 30 % with the following change in Painter/Render.cpp: void BufferPainter::ClearOp(const RGBA& color) { // UPP::Fill(~*ip, color, ip->GetLength()); FillRGBA(~*ip, color, ip->GetLength()); ip->SetKind(color.a == 255 ? IMAGE_OPAQUE : IMAGE_ALPHA); } And in Painter/Fillers.h: namespace Upp { // Add the following line: #define FillRGBA(a,b,c) memsetd((a),*(dword*)&(b),(c)) struct SolidFiller : Rasterizer::Filler { This may be significant in some usage scenarios as it can currently take e.g. 4.5 milliseconds to clear a 4K ImageBuffer before drawing to it. This can now be reduced to 2.8 milliseconds. Now this is really interesting. Fill for RGBA* is actually one that is optimized for filling huge blocks. I will need to do some benchmarks...
Hi, Benchmarking and tuning is exactly what I did through yesterday (and beyond). I worked with both CLANGx64 and MSBT19x64. I worked out a bunch of optimized fillers until it turned out that memsetd() wins easily on large blocks and mostly on smaller blocks too. Especially on MSBT19x64 there does not seem to be a way to beat memsetd(). On CLANGx64 small transfer of one or two items was slightly faster, but on larger blocks memsetd() won again. Interestingly, CLANGx64 was a lot faster than MSBT19x64 for any of my own block transfer attempts, but still could not beat memsetd(). Best regards, Tom
Hm, MacOS 2,3 GHz Intel Core i5 TIMING Fill : 1.52 s - 1.52 ms ( 1.52 s / 1000 ), min: 1.00 ms, max: 2.00 ms, nesting: 0 - 1000 TIMING memsetd : 1.53 s - 1.53 ms ( 1.53 s / 1000 ), min: 1.00 ms, max: 12.00 ms, nesting: 0 - 1000 That's quite weird... Mirek
Hi, Yes, CPU is likely the major player here. I took the liberty to modify TimingInspector to get finer granularity for timing using usecs(). The modified testcase can be found below. I get the following results on my Core i7 + Windows 10 professional x64. Now we can focus on the best round 'min:' to better avoid other tasks' effect. As you can see memsetd on MSBT19x64 is quite amazing performer. MSBT19x64, Intel Core i7: TIMING memsetd : 1.45 s - 1.45 ms ( 1.45 s / 1000 ), min: 1.15 ms, max: 5.25 ms, nesting: 0 - 1000 TIMING Fill : 3.73 s - 3.73 ms ( 3.73 s / 1000 ), min: 3.25 ms, max: 9.92 ms, nesting: 0 - 1000 CLANGx64, Intel Core i7: TIMING memsetd : 3.85 s - 3.85 ms ( 3.85 s / 1000 ), min: 3.35 ms, max: 10.36 ms, nesting: 0 - 1000 TIMING Fill : 3.87 s - 3.87 ms ( 3.87 s / 1000 ), min: 3.38 ms, max: 11.33 ms, nesting: 0 - 1000 I guess that in my larger program the optimizations did not work this well as the Fill would have performed at around 5 ms level for this size of a buffer. Anyway here's the modified benchmark. #include <CtrlLib/CtrlLib.h> using namespace Upp; class UTimingInspector { protected: static bool active; const char *name; int call_count; int64 total_time; int64 min_time; int64 max_time; int max_nesting; int all_count; StaticMutex mutex; public: UTimingInspector(const char *name = NULL); // Not String !!! ~UTimingInspector(); void Add(dword time, int nesting); String Dump(); class Routine { public: Routine(UTimingInspector& stat, int& nesting) : nesting(nesting), stat(stat) { start_time = usecs(); nesting++; } ~Routine() { nesting--; stat.Add(start_time, nesting); } protected: int64 start_time; int& nesting; UTimingInspector& stat; }; static void Activate(bool b) { active = b; } }; bool UTimingInspector::active = true; static UTimingInspector s_zero; // time of Start / End without actual body to measure UTimingInspector::UTimingInspector(const char *_name) { name = _name ? _name : ""; all_count = call_count = max_nesting = min_time = max_time = total_time = 0; static bool init; if(!init) { #if defined(PLATFORM_WIN32) && !defined(PLATFORM_WINCE) timeBeginPeriod(1); #endif init = true; } } UTimingInspector::~UTimingInspector() { if(this == &s_zero) return; Mutex::Lock __(mutex); StdLog() << Dump() << "\r\n"; } void UTimingInspector::Add(dword time, int nesting) { time = usecs() - time; Mutex::Lock __(mutex); if(!active) return; all_count++; if(nesting > max_nesting) max_nesting = nesting; if(nesting == 0) { total_time += time; if(call_count++ == 0) min_time = max_time = time; else { if(time < min_time) min_time = time; if(time > max_time) max_time = time; } } } String UTimingInspector::Dump() { Mutex::Lock __(mutex); String s = Sprintf("TIMING %-15s: ", name); if(call_count == 0) return s + "No active hit"; ONCELOCK { int w = GetTickCount(); while(GetTickCount() - w < 200) { // measure profiling overhead thread_local int nesting = 0; UTimingInspector::Routine __(s_zero, nesting); } } double tm = max(0.0, double(total_time) / call_count / 1000000 - double(s_zero.total_time) / s_zero.call_count / 1000000); return s + timeFormat(tm * call_count) + " - " + timeFormat(tm) + " (" + timeFormat((double)total_time / 1000000) + " / " + Sprintf("%d )", call_count) + ", min: " + timeFormat((double)min_time / 1000000) + ", max: " + timeFormat((double)max_time / 1000000) + Sprintf(", nesting: %d - %d", max_nesting, all_count); } #define RUTIMING(x) \ static UTimingInspector COMBINE(sTmStat, __LINE__)(x); \ static thread_local int COMBINE(sTmStatNesting, __LINE__); \ UTimingInspector::Routine COMBINE(sTmStatR, __LINE__)(COMBINE(sTmStat, __LINE__), COMBINE(sTmStatNesting, __LINE__)) GUI_APP_MAIN { Color c = Red(); int len = 4000 * 2000; Buffer<RGBA> b(len); for(int i = 0; i < 1000; i++) { { RUTIMING("Fill"); Fill(b, c, len); } { RUTIMING("memsetd"); memsetd(b, *(dword*)&(c), len); } } } Best regards, Tom
Hello, A quick test on an older AMD FX 6100, six core processor. 3.2 GHZ (naturally, it is slower): // GCC (x64, latest ver.) TIMING Fill : 7,53 s - 7,53 ms ( 7,53 s / 1000 ), min: 7,00 ms, max: 9,00 ms, nesting: 0 - 1000 TIMING memsetd : 6,31 s - 6,31 ms ( 6,31 s / 1000 ), min: 6,00 ms, max: 18,00 ms, nesting: 0 - 1000 ---- // CLANG(x64, latest ver.) TIMING Fill : 7,07 s - 7,07 ms ( 7,07 s / 1000 ), min: 6,00 ms, max: 10,00 ms, nesting: 0 - 1000 TIMING memsetd : 7,07 s - 7,07 ms ( 7,08 s / 1000 ), min: 6,00 ms, max: 17,00 ms, nesting: 0 - 1000 ----- Best regards, Oblivion
Experimenting with parallel: #include <CtrlLib/CtrlLib.h> using namespace Upp; void CoFill(RGBA *t, RGBA c, int len) { const int CHUNK = 1024; std::atomic<int> ii(0); CoDo([&] { for(;;) { int pos = CHUNK * ii++; if(pos >= len) break; Fill(t + pos, c, min(CHUNK, len - pos)); } }); } GUI_APP_MAIN { Color c = Red(); int len = 4000 * 2000; Buffer<RGBA> b(len); for(int i = 0; i < 10; i++) { { RTIMING("memsetd"); memsetd(b, *(dword*)&(c), len); } { RTIMING("Fill"); Fill(b, c, len); } { RTIMING("CoFill"); CoFill(b, c, len); } } } TIMING CoFill : 19.00 ms - 1.90 ms (19.00 ms / 10 ), min: 1.00 ms, max: 3.00 ms, nesting: 0 - 10 TIMING Fill : 31.00 ms - 3.10 ms (31.00 ms / 10 ), min: 3.00 ms, max: 4.00 ms, nesting: 0 - 10 TIMING memsetd : 30.00 ms - 3.00 ms (30.00 ms / 10 ), min: 2.00 ms, max: 5.00 ms, nesting: 0 - 10 To try that on different CPU, Rapsberry PI 4 numbers: TIMING CoFill : 145.00 ms - 14.50 ms (145.00 ms / 10 ), min: 14.00 ms, max: 15.00 ms, nesting: 0 - 10 TIMING Fill : 225.00 ms - 22.50 ms (225.00 ms / 10 ), min: 22.00 ms, max: 24.00 ms, nesting: 0 - 10 TIMING memsetd : 184.00 ms - 18.40 ms (184.00 ms / 10 ), min: 11.00 ms, max: 77.00 ms, nesting: 0 - 10
Hi Mirek, While interesting, I found that a plain memset() is way faster than memsetd() or Fill(). Just filling with 0xff (as the RGBA is for white) you will get a superior speed. I currently use memset() for a clear white on a ImageBuffer before giving it to BufferPainter. For more complex fill colors, I guess, the apex_memmove / memcpy code could be investigated for a more optimal result. (I posted a link to the apex code here on the forum briefly before release of 2020.1 Best regards, Tom
Tom1 wrote on Fri, 15 May 2020 10:18 While interesting, I found that a plain memset() is way faster than memsetd() or Fill(). Just filling with 0xff (as the RGBA is for white) you will get a superior speed. I currently use memset() for a clear white on a ImageBuffer before giving it to BufferPainter. For more complex fill colors, I guess, the apex_memmove / memcpy code could be investigated for a more optimal result. (I posted a link to the apex code here on the forum briefly before release of 2020.1 Best regards, Tom With CLANG, memset performance is about the same. However, with MSVC, it really is pretty damn fast. I have digged into the code and the key ingredient seems to be MOVNTPS instruction, which means the code could be easily adapted to setting dwords. I just need to understand MT implications mentioned here: https://www.felixcloutier.com/x86/movntps It also might be questionable how this will affect the performance down the road (data not being in cache and everything...) Mirek
At the time I was testing with the memset -- if I remember correctly -- on Windows + CLANG the memset with zero value was very efficient too, but the rest of the set values were slower. So, there must be some special optimized implementation for zeroing memory on CLANG too. BR, Tom
Here we go: void SSEFill2(RGBA *t, RGBA c, int len) { if(len >= 512) { while((uintptr_t)t & 63) { // align to cache line *t++ = c; len--; } dword m[4]; m[0] = m[1] = m[2] = m[3] = *(dword*)&(c); __m128d val = _mm_loadu_pd((double *)m); while(len >= 16) { _mm_stream_pd((double *)t, val); _mm_stream_pd((double *)(t + 4), val); _mm_stream_pd((double *)(t + 8), val); _mm_stream_pd((double *)(t + 12), val); t += 16; len -= 16; } _mm_sfence(); } Fill(t, c, len); } TIMING CoFill : 42.00 ms - 2.10 ms (42.00 ms / 20 ), min: 1.00 ms, max: 3.00 ms, nesting: 0 - 20 TIMING SSEFill2 : 16.00 ms - 799.98 us (16.00 ms / 20 ), min: 0.00 ns, max: 1.00 ms, nesting: 0 - 20 TIMING SSEFill : 55.00 ms - 2.75 ms (55.00 ms / 20 ), min: 2.00 ms, max: 3.00 ms, nesting: 0 - 20 TIMING Fill : 56.00 ms - 2.80 ms (56.00 ms / 20 ), min: 2.00 ms, max: 3.00 ms, nesting: 0 - 20 TIMING memsetd : 52.00 ms - 2.60 ms (52.00 ms / 20 ), min: 2.00 ms, max: 3.00 ms, nesting: 0 - 20
And we have a winner!! Also, please take a look at MSBT19 and MSBT19x64 for this too. It looks like this code only works with CLANG and CLANGx64 on Windows. (Have not checked on Linux yet.) Additionally, plain memset, memsets and memsetd -variants would be useful for various tasks, as their efficiency varies depending on the compiler. Thanks and best regards, Tom EDIT: I mean it does not compile on MSBT...
On linux with the relatively old AMD Athlon FX 6100. Works with both GCC (9.3) and CLANG (10.0). Requires #include <smmintrin.h>: GCC: TIMING SSEFill2 : 43,99 ms - 4,40 ms (44,00 ms / 10 ), min: 4,00 ms, max: 5,00 ms, nesting: 0 - 10 TIMING CoFill : 55,99 ms - 5,60 ms (56,00 ms / 10 ), min: 5,00 ms, max: 6,00 ms, nesting: 0 - 10 TIMING Fill : 75,99 ms - 7,60 ms (76,00 ms / 10 ), min: 7,00 ms, max: 8,00 ms, nesting: 0 - 10 TIMING memsetd : 66,99 ms - 6,70 ms (67,00 ms / 10 ), min: 5,00 ms, max: 17,00 ms, nesting: 0 - 10 CLANG: TIMING SSEFill2 : 45,99 ms - 4,60 ms (46,00 ms / 10 ), min: 4,00 ms, max: 7,00 ms, nesting: 0 - 10 TIMING CoFill : 55,99 ms - 5,60 ms (56,00 ms / 10 ), min: 5,00 ms, max: 6,00 ms, nesting: 0 - 10 TIMING Fill : 65,99 ms - 6,60 ms (66,00 ms / 10 ), min: 6,00 ms, max: 10,00 ms, nesting: 0 - 10 TIMING memsetd : 78,99 ms - 7,90 ms (79,00 ms / 10 ), min: 5,00 ms, max: 23,00 ms, nesting: 0 - 10
Hi, Thanks Oblivion; the #include <smmintrin.h> was exactly what was needed on Windows + CLANG too... Here are the results for the 4k RGBA fill on Windows 10 x64 on Core i9: MSBT19: TIMING SSEFill2 : 1.30 s - 1.30 ms ( 1.30 s / 1000 ), min: 1.03 ms, max: 1.99 ms, nesting: 0 - 1000 TIMING Fill : 1.13 s - 1.13 ms ( 1.13 s / 1000 ), min: 841.00 us, max: 3.04 ms, nesting: 0 - 1000 MSBT19x64: TIMING SSEFill2 : 906.90 ms - 906.90 us (906.93 ms / 1000 ), min: 846.00 us, max: 1.67 ms, nesting: 0 - 1000 TIMING Fill : 2.34 s - 2.34 ms ( 2.34 s / 1000 ), min: 2.21 ms, max: 4.69 ms, nesting: 0 - 1000 CLANG: TIMING SSEFill2 : 935.97 ms - 935.97 us (936.02 ms / 1000 ), min: 854.00 us, max: 1.67 ms, nesting: 0 - 1000 TIMING Fill : 2.44 s - 2.44 ms ( 2.44 s / 1000 ), min: 2.25 ms, max: 4.74 ms, nesting: 0 - 1000 CLANGx64: TIMING SSEFill2 : 934.45 ms - 934.45 us (934.47 ms / 1000 ), min: 854.00 us, max: 1.77 ms, nesting: 0 - 1000 TIMING Fill : 2.20 s - 2.20 ms ( 2.20 s / 1000 ), min: 1.98 ms, max: 5.97 ms, nesting: 0 - 1000 Looks very good indeed! MSBT19 on the other hand looks surprising... Best regards, Tom
Tom1 wrote on Fri, 15 May 2020 12:08 Additionally, plain memset, memsets and memsetd -variants would be useful for various tasks, as their efficiency varies depending on the compiler. What about this: void FillCacheLines(void *cache_aligned_ptr, void *data16, int count) { dword *t = (dword *)cache_aligned_ptr; __m128d val = _mm_loadu_pd((double *)data16); dword *e = t + 16 * count; while(t < e) { _mm_stream_pd((double *)t, val); _mm_stream_pd((double *)(t + 4), val); _mm_stream_pd((double *)(t + 8), val); _mm_stream_pd((double *)(t + 12), val); t += 16; } _mm_sfence(); } template <class T> void MemSet(void *dest, T data, int len) { static_assert(sizeof(T) == 1 || sizeof(T) == 2 || sizeof(T) == 4 || sizeof(T) == 8 || sizeof(T) == 16, "invalid sizeof"); T *t = (T *)dest; if(len * sizeof(T) > 550) { while((uintptr_t)t & 63) { // align to cache line *t++ = data; len--; } const int itemn = 16 / sizeof(T); const int per_cache_line = 4 * itemn; T m[itemn]; for(int i = 0; i < itemn; i++) m[i] = data; int count = len / per_cache_line; FillCacheLines(t, m, count); len -= per_cache_line * count; } while(len >= 16) { t[0] = data; t[1] = data; t[2] = data; t[3] = data; t[4] = data; t[5] = data; t[6] = data; t[7] = data; t[8] = data; t[9] = data; t[10] = data; t[11] = data; t[12] = data; t[13] = data; t[14] = data; t[15] = data; t += 16; len -= 16; } switch(len) { case 15: t[14] = data; case 14: t[13] = data; case 13: t[12] = data; case 12: t[11] = data; case 11: t[10] = data; case 10: t[9] = data; case 9: t[8] = data; case 8: t[7] = data; case 7: t[6] = data; case 6: t[5] = data; case 5: t[4] = data; case 4: t[3] = data; case 3: t[2] = data; case 2: t[1] = data; case 1: t[0] = data; } }
Mirek, Yes, absolutely beautiful! The results for the set including the new MemSet() on Win10x64 on Core i9 are: MSBT19: TIMING MemSet : 831.06 ms - 831.06 us (831.13 ms / 1000 ), min: 779.00 us, max: 1.72 ms, nesting: 0 - 1000 TIMING SSEFill2 : 1.21 s - 1.21 ms ( 1.21 s / 1000 ), min: 1.00 ms, max: 2.19 ms, nesting: 0 - 1000 TIMING Fill : 915.70 ms - 915.70 us (915.76 ms / 1000 ), min: 859.00 us, max: 3.49 ms, nesting: 0 - 1000 MSBT19x64: TIMING MemSet : 818.33 ms - 818.33 us (818.36 ms / 1000 ), min: 777.00 us, max: 1.71 ms, nesting: 0 - 1000 TIMING SSEFill2 : 899.74 ms - 899.74 us (899.77 ms / 1000 ), min: 854.00 us, max: 1.78 ms, nesting: 0 - 1000 TIMING Fill : 2.29 s - 2.29 ms ( 2.29 s / 1000 ), min: 2.21 ms, max: 4.51 ms, nesting: 0 - 1000 CLANG: TIMING MemSet : 835.39 ms - 835.39 us (835.45 ms / 1000 ), min: 790.00 us, max: 1.51 ms, nesting: 0 - 1000 TIMING SSEFill2 : 918.63 ms - 918.63 us (918.68 ms / 1000 ), min: 872.00 us, max: 1.47 ms, nesting: 0 - 1000 TIMING Fill : 2.36 s - 2.36 ms ( 2.36 s / 1000 ), min: 2.28 ms, max: 5.45 ms, nesting: 0 - 1000 CLANGx64: TIMING MemSet : 838.86 ms - 838.86 us (838.89 ms / 1000 ), min: 787.00 us, max: 1.70 ms, nesting: 0 - 1000 TIMING SSEFill2 : 921.49 ms - 921.49 us (921.51 ms / 1000 ), min: 870.00 us, max: 1.84 ms, nesting: 0 - 1000 TIMING Fill : 2.10 s - 2.10 ms ( 2.10 s / 1000 ), min: 2.01 ms, max: 5.00 ms, nesting: 0 - 1000 I trust you can now make all the different fillers through U++ to use this new code... right? Thanks and best regards, Tom
Hi Mirek, The game is not over yet, I'm afraid. I did some additional benchmarking with varying buffer lengths to set. It get's more complicated... RGBA c = Red(); int bsize=8*1024*1024; Buffer<RGBA> b(bsize,(RGBA)Blue()); String result="\"N\",\"Fill()\",\"memsetd()\",\"MemSet()\"\r\n"; for(int len=1;len<=bsize;len*=2){ int maximum=1000000000/len; int64 t0=usecs(); for(int i = 0; i < maximum; i++) Fill(~b, c, len); int64 t1=usecs(t0); t0=usecs(); for(int i = 0; i < maximum; i++) memsetd(~b, *(dword*)&(c), len); int64 t2=usecs(t0); t0=usecs(); for(int i = 0; i < maximum; i++) MemSet(~b, c, len); int64 t3=usecs(t0); result.Cat(Format("%d,%f,%f,%f\r\n",len,1000.0*t1/maximum,1000.0*t2/maximum,1000.0*t3/maximum)); } SaveFile(GetHomeDirFile("Desktop/memset.csv"),result); Now, if you import the resulting memset.csv to your spreadsheet program and create a log-log plot, you will see that the different buffer lengths have a huge impact on the performance of each algorithm. As filling lengths can be quite diverse, I think we need to think about some combination of the different algorithms. Additionally, we need to look at the results on different CPUs. I will keep tinkering on this one for a while here. (Now I'm running on Core i7 here at home, so this one I can test easily, and also the Core i9 at the office every now and then, as the situation is what it is...) Best regards, Tom
Hi, I've worked on optimizing the new_memsetd() operation through various buffer sizes up to 8M and here's the best I can come up with (at least this night...). With CLANG it seems to be beneficial to use the Mirek's new MemSet() for buffer sizes above about 1M, but below that and also with MSBT19 / MSBT19x64 the result is better without. (This algorithm is especially efficient with small fills and therefore should work well as a BufferPainter filler too.) For best results, there are separate versions for 32-bit and 64-bit code. (The '#ifdef WIN64' obviously only works on Windows, but I think there was some other flag on Linux for detecting a 64-bit environment. Please apply that flag, whatever it is, if you test on Linux, etc...) #ifdef WIN64 inline void new_memsetd(dword *t, dword data, int len){ #ifdef COMPILER_CLANG if(len>1024*1024){ MemSet(t,data,len); return; } #endif if(len&1) *t++=data; len>>=1; uint64 *w=(uint64*)t; uint64 q=data; q = (q << 32) | data; switch(len) { default:{ uint64 *lim = w + len; while(w < lim) *w++ = q; break; } case 16: w[15] = q; case 15: w[14] = q; case 14: w[13] = q; case 13: w[12] = q; case 12: w[11] = q; case 11: w[10] = q; case 10: w[9] = q; case 9: w[8] = q; case 8: w[7] = q; case 7: w[6] = q; case 6: w[5] = q; case 5: w[4] = q; case 4: w[3] = q; case 3: w[2] = q; case 2: w[1] = q; case 1: w[0] = q; } } #else inline void new_memsetd(dword *t, dword data, int len){ #ifdef COMPILER_CLANG if(len>1024*1024){ MemSet(t,data,len); return; } #endif switch(len) { default:{ dword *lim = t + len; while(t < lim) *t++ = data; break; } case 16: t[15] = data; case 15: t[14] = data; case 14: t[13] = data; case 13: t[12] = data; case 12: t[11] = data; case 11: t[10] = data; case 10: t[9] = data; case 9: t[8] = data; case 8: t[7] = data; case 7: t[6] = data; case 6: t[5] = data; case 5: t[4] = data; case 4: t[3] = data; case 3: t[2] = data; case 2: t[1] = data; case 1: t[0] = data; } } #endif The updated benchmarking code: RGBA c = Red(); int bsize=8*1024*1024; Buffer<RGBA> b(bsize,(RGBA)Blue()); String result="\"N\",\"Fill()\",\"new_memsetd()\",\"MemSet()\"\r\n"; for(int len=1;len<=bsize;){ int maximum=100000000/len; int64 t0=usecs(); for(int i = 0; i < maximum; i++) Fill(~b, c, len); int64 t1=usecs(); for(int i = 0; i < maximum; i++) new_memsetd((dword*)~b, *(dword*)&(c), len); int64 t2=usecs(); for(int i = 0; i < maximum; i++) MemSet(~b, c, len); int64 t3=usecs(); result.Cat(Format("%d,%f,%f,%f\r\n",len,1000.0*(t1-t0)/maximum,1000.0*(t2-t1)/maximum,1000.0*(t3-t2)/maximum)); if(len<32) len++; else len*=2; } SaveFile(GetHomeDirFile("Desktop/memset.csv"),result); Again, I suggest you plot your results using a log-log chart to clearly see the performance with all different block sizes. If you have some time to spare, please let me know how this works for you. Best regards, Tom
Hi, Interestingly, the FillRGBA() that can be found in the current BufferPainter Fillers, is a real performer. It wins below 1M dwords just about anything else. However, Mireks new MemSet is the winner thereafter. This applies on Windows 10 x64 to CLANG/CLANGx64/MSBT19 on my Core i7. Only MSBT19x64 has a different situation and the following code tries to optimize that, in addition to combining FillRGBA and MemSet for the other compilers: #if defined(WIN64) && defined(COMPILER_MSC) // for MSBT19x64 only: inline void new_memsetd(void *b, dword data, int len){ dword *t=(dword *)b; switch(len){ case 6: t[5] = data; case 5: t[4] = data; case 4: t[3] = data; case 3: t[2] = data; case 2: t[1] = data; case 1: t[0] = data; case 0: return; default:{ if(len&1) *t++=data; len>>=1; uint64 *w=(uint64*)t; uint64 q=*(dword*)&data; q |= (q << 32); switch(len) { default:{ uint64 *lim = w + len - 32; while(w < lim) *w++ = q; } case 32: w[31] = q; case 31: w[30] = q; case 30: w[29] = q; case 29: w[28] = q; case 28: w[27] = q; case 27: w[26] = q; case 26: w[25] = q; case 25: w[24] = q; case 24: w[23] = q; case 23: w[22] = q; case 22: w[21] = q; case 21: w[20] = q; case 20: w[19] = q; case 19: w[18] = q; case 18: w[17] = q; case 17: w[16] = q; case 16: w[15] = q; case 15: w[14] = q; case 14: w[13] = q; case 13: w[12] = q; case 12: w[11] = q; case 11: w[10] = q; case 10: w[9] = q; case 9: w[8] = q; case 8: w[7] = q; case 7: w[6] = q; case 6: w[5] = q; case 5: w[4] = q; case 4: w[3] = q; case 3: w[2] = q; case 2: w[1] = q; case 1: w[0] = q; } } } } #else inline void new_memsetd(void *b, dword data, int len){ if(len<=1024*1024) FillRGBA((RGBA*)b,*(RGBA*)&data,len); else MemSet(b,data,len); } #endif The benchmarking code for various fill sizes now looks like this: RGBA c = Red(); int bsize=8*1024*1024; Buffer<RGBA> b(bsize,(RGBA)Blue()); String result="\"N\",\"Fill()\",\"new_memsetd()\",\"MemSet()\",\"FillRGBA()\"\r\n"; for(int len=1;len<=bsize;){ int maximum=100000000/len; int64 t0=usecs(); for(int i = 0; i < maximum; i++) Fill(~b, c, len); int64 t1=usecs(); for(int i = 0; i < maximum; i++) new_memsetd(~b, *(dword*)&c, len); int64 t2=usecs(); for(int i = 0; i < maximum; i++) MemSet(~b, c, len); int64 t3=usecs(); for(int i = 0; i < maximum; i++) FillRGBA(~b, c, len); int64 t4=usecs(); result.Cat(Format("%d,%f,%f,%f,%f\r\n",len,1000.0*(t1-t0)/maximum,1000.0*(t2-t1)/maximum,1000.0*(t3-t2)/maximum,1000.0*(t4-t3)/maximum)); if(len<64) len++; else len*=2; } SaveFile(GetHomeDirFile("Desktop/memset.csv"),result); Best regards, Tom
Tom1 wrote on Sat, 16 May 2020 01:59 With CLANG it seems to be beneficial to use the Mirek's new MemSet() for buffer sizes above about 1M I guess L2 cache size plays a role here. The new trick bypasses the cache so kicks in when cache is exhausted... Mirek
mirek wrote on Sun, 17 May 2020 09:47 Tom1 wrote on Sat, 16 May 2020 01:59 With CLANG it seems to be beneficial to use the Mirek's new MemSet() for buffer sizes above about 1M I guess L2 cache size plays a role here. The new trick bypasses the cache so kicks in when cache is exhausted... Mirek Hi, Where can I find the new trick? BR, Tom
Ah, by "trick" I mean using using non-temporal move instruction which we have found in memset.... Mirek
Mirek, Also, please check my previous new_memsetd() above using MSBT19x64 for reference. Preferably also with short transfers (1-64). Best regards, Tom
Mirek, Please check out this one. It features better performance on MSBT19 / MSBT19x64 with low counts, and works well on CLANG/CLANGx64 too: inline void new_memset128(void *b, dword data, int len){ switch(len){ case 4: ((dword *)b)[3] = data; case 3: ((dword *)b)[2] = data; case 2: ((dword *)b)[1] = data; case 1: ((dword *)b)[0] = data; case 0: return; } __m128i q = _mm_set1_epi32(*(int*)&data); __m128i *w = (__m128i*)b; switch(len>>2){ default:{ __m128i *e = (__m128i*)b + (len>>2) - 4; if(len <= 2*1024*1024){ while(w<e){ _mm_storeu_si128(w++, q); _mm_storeu_si128(w++, q); _mm_storeu_si128(w++, q); _mm_storeu_si128(w++, q); } } else{ while(w<e){ _mm_stream_si128(w++, q); _mm_stream_si128(w++, q); _mm_stream_si128(w++, q); _mm_stream_si128(w++, q); } } } case 4: _mm_storeu_si128(w++, q); case 3: _mm_storeu_si128(w++, q); case 2: _mm_storeu_si128(w++, q); case 1: _mm_storeu_si128(w++, q); } switch(len&3){ case 3: ((dword *)b)[len-3] = data; case 2: ((dword *)b)[len-2] = data; case 1: ((dword *)b)[len-1] = data; } } Best regards, Tom EDIT: Fine tuning...
Tom1 wrote on Sun, 17 May 2020 23:25 Mirek, Please check out this one. It features better performance on MSBT19 / MSBT19x64 with low counts, and works well on CLANG/CLANGx64 too: I think there are 2 issues: - Cache bypass starts at 8MB. - Missing alignment adjustment for cache bypass. - I might be wrong, but why is there " - 4": __m128i *e = (__m128i*)t + (len>>2) - 4; ? But yes, it hits something for MSC compiler... Mirek
Hi, Yes, you're right: The alignment should be handled. I'll take a look at it... (just need to minimize the code size in order to avoid penalty for short transfers. It is extremely sensitive.) The cache limit is intentionally 8MB as this is the sweet spot for my Core i7. Probably should get this value from the system to optimize the correct threshold. The -4 compensates the rest of the samples handled within the leaked default in the switch. (The below cases do the trick). Best regards, Tom
Hi, Alignment corrected. (Caused obviously a lot of rearranging things to obtain balance.) Threshold is still at 8M, but feel free to experiment. inline void new_memset128(void *b, dword data, int len){ switch(len){ case 5: ((dword *)b)[4] = data; case 4: ((dword *)b)[3] = data; case 3: ((dword *)b)[2] = data; case 2: ((dword *)b)[1] = data; case 1: ((dword *)b)[0] = data; case 0: return; } __m128i q = _mm_set1_epi32(*(int*)&data); __m128i *w = (__m128i*)b; __m128i *e = (__m128i*)b + (len>>2); if(len <= 2*1024*1024 || ((uintptr_t)b&3)){ while(w<e-1){ _mm_storeu_si128(w++, q); _mm_storeu_si128(w++, q); } if(w<e) _mm_storeu_si128(w++, q); } else{ int s=(-((int)((uintptr_t)b)>>2))&0x3; switch(s){ case 3: ((dword *)b)[2] = data; case 2: ((dword *)b)[1] = data; case 1: ((dword *)b)[0] = data; } w = (__m128i*) ((dword*)b + s); while(w<e) _mm_stream_si128(w++, q); _mm_sfence(); } switch(len&3){ case 3: ((dword *)b)[len-3] = data; case 2: ((dword *)b)[len-2] = data; case 1: ((dword *)b)[len-1] = data; } } Best regards, Tom
So I kept digging and found that the reason why Fill3 performed great with CLANG and less great with MSC was that CLANG understand what I mean with that ugly array based code to fill 4 color values into the xmm register while MSC really created that 'm' array, stored 4 values into memory and then fetched them into xmm... Fixed Fill3 seems to perform well with MSC too: void Fill3(RGBA *t, RGBA c, int len) { __m128i val4 = _mm_set1_epi32(*(int*)&c); auto Set4 = [&](int at) { _mm_storeu_si128((__m128i *)(t + at), val4); }; auto Set4S = [&](int at) { _mm_stream_si128((__m128i *)(t + at), val4); }; if(len >= 16) { if(len > 1024*1024 / 16 && ((uintptr_t)t & 3) == 0) { // for really huge data, bypass the cache while((uintptr_t)t & 15) { // align to 16 bytes for SSE *t++ = c; len--; } do { Set4S(0); Set4S(4); Set4S(8); Set4S(12); t += 16; len -= 16; } while(len >= 16); _mm_sfence(); } else do { Set4(0); Set4(4); Set4(8); Set4(12); t += 16; len -= 16; } while(len >= 16); } if(len & 8) { Set4(0); Set4(4); t += 8; } if(len & 4) { Set4(0); t += 4; } if(len & 2) { t[0] = t[1] = c; t += 2; } if(len & 1) t[0] = c; } Mirek
This variation of basically the same thing seems a tiny bit faster: void Fill3a(RGBA *t, RGBA c, int len) { __m128i val4 = _mm_set1_epi32(*(int*)&c); auto Set4 = [&](int at) { _mm_storeu_si128((__m128i *)(t + at), val4); }; auto Set4S = [&](int at) { _mm_stream_si128((__m128i *)(t + at), val4); }; if(len >= 32) { if(len > 1024*1024 / 16 && ((uintptr_t)t & 3) == 0) { // for really huge data, bypass the cache while((uintptr_t)t & 15) { // align to 16 bytes for SSE *t++ = c; len--; } do { Set4S(0); Set4S(4); Set4S(8); Set4S(12); Set4S(16); Set4S(20); Set4S(24); Set4S(28); t += 32; len -= 32; } while(len >= 32); _mm_sfence(); } else do { Set4(0); Set4(4); Set4(8); Set4(12); Set4(16); Set4(20); Set4(24); Set4(28); t += 32; len -= 32; } while(len >= 32); } if(len & 16) { Set4(0); Set4(4); Set4(8); Set4(12); t += 16; } if(len & 8) { Set4(0); Set4(4); t += 8; } if(len & 4) { Set4(0); t += 4; } if(len & 2) { t[0] = t[1] = c; t += 2; } if(len & 1) t[0] = c; }
You can actually do alignment without branching there (that I got from studying memset code . I guess that is the last thing to try now
mirek wrote on Mon, 18 May 2020 14:53 You can actually do alignment without branching there (that I got from studying memset code . I guess that is the last thing to try now Hi, Sounds good, but seems hard to squeeze speed from ... (tried quite a while now). BR, Tom
Mirek, Here it is: The unconditional alignment. I took your idea, ditched my own, and modified your Fill3a as follows: void inline Fill3T(void *b, dword data, int len){ switch(len){ case 3: ((dword *)b)[2] = data; case 2: ((dword *)b)[1] = data; case 1: ((dword *)b)[0] = data; case 0: return; } __m128i q = _mm_set1_epi32(*(int*)&data); __m128i *w = (__m128i*)b; if(len >= 32) { __m128i *e = (__m128i*)b + (len>>2) - 8; if(len > 1024*1024 / 16 && ((uintptr_t)w & 3) == 0) { // for really huge data, bypass the cache _mm_storeu_si128(w, q); // Head align int s=(-((int)((uintptr_t)b)>>2))&0x3; w = (__m128i*) ((dword*)b) + s; do { _mm_stream_si128(w++, q); _mm_stream_si128(w++, q); _mm_stream_si128(w++, q); _mm_stream_si128(w++, q); _mm_stream_si128(w++, q); _mm_stream_si128(w++, q); _mm_stream_si128(w++, q); _mm_stream_si128(w++, q); }while(w<=e); _mm_sfence(); } else do { _mm_storeu_si128(w++, q); _mm_storeu_si128(w++, q); _mm_storeu_si128(w++, q); _mm_storeu_si128(w++, q); _mm_storeu_si128(w++, q); _mm_storeu_si128(w++, q); _mm_storeu_si128(w++, q); _mm_storeu_si128(w++, q); }while(w<=e); } if(len & 16) { _mm_storeu_si128(w++, q); _mm_storeu_si128(w++, q); _mm_storeu_si128(w++, q); _mm_storeu_si128(w++, q); } if(len & 8) { _mm_storeu_si128(w++, q); _mm_storeu_si128(w++, q); } if(len & 4) { _mm_storeu_si128(w, q); } _mm_storeu_si128((__m128i*) (((dword*)b) + len - 4), q); // Tail align } I made some other changes too and this one is slightly faster on short transfers while equals Fill3a() on longer ones. The improvement is more significant on MSBT19 / MSBT19x64. In order to get real fast short transfers, the function must be 'inline'. I think this necessitates two variants of the final function. (I have seen that BufferPainter paints most of the time with really short fills, so inlining really makes a difference there.) Best regards, Tom P.S. My cache threshold is still at 8M...
Well, my full idea was to align for len >= 32 always and MAYBE have some benefit from the fact that stores are now aligned (even perhaps use aligned version). Sources diverge on actuall performance, but it might be around 10%. In any case, MSC memset does this... Mirek
Tom1 wrote on Mon, 18 May 2020 17:08 In order to get real fast short transfers, the function must be 'inline'. I think this necessitates two variants of the final function. (I have seen that BufferPainter paints most of the time with really short fills, so inlining really makes a difference there.) Well, CLANG inlines all Fill3 variants without me asking him to do it, so I guess I have zero problems to have it in the header... Quote: P.S. My cache threshold is still at 8M... What are your CPU L1/L2/L3 caches? What happens if you move that to 1M, 12M, 16M? (I mean, how much penalty you get?) Mirek
Hi, My CPU here is Intel(R) Core(TM) i7-4790K: https://ark.intel.com/content/www/us/en/ark/products/80807/i ntel-core-i7-4790k-processor-8m-cache-up-to-4-40-ghz.html Not surprisingly, they say it has an 8M 'smart cache'. Please find attached two CSV files portraying execution time in ns for each call in average. The length is in dwords. Fill3a is there for reference and Fill3T is using 64 dword threshold for streaming in one and 2M dword (8MB) threshold in the other file. While not portrayed here, increasing the threshold above 32MB decreases the performance from 1.5 ms to 3.6 ms for a 32 MB buffer. Best regards, Tom
Hi, It looks that luckily CPUID reveals cache information: https://www.intel.com/content/www/us/en/architecture-and-tec hnology/64-ia-32-architectures-software-developer-vol-2a-man ual.html Initial value in EAX 80000006H ECX: Bits 07 - 00: Cache Line size in bytes. Bits 11 - 08: Reserved. Bits 15 - 12: L2 Associativity field. Bits 31 - 16: Cache size in 1K units. Could we use this? Best regards, Tom
Hi Mirek, Something like this, maybe... I'm not quite sure as this method reports 16M cache for me -- although this works quite well for me: static int cachesize=999; INITBLOCK{ #ifdef COMPILER_MSC int cpuInfo[4]; Zero(cpuInfo); __cpuid(cpuInfo, 0x80000006); #else unsigned int cpuInfo[4]; Zero(cpuInfo); __get_cpuid(0x80000006, &cpuInfo[0], &cpuInfo[1], &cpuInfo[2], &cpuInfo[3]); #endif cachesize=1024*(cpuInfo[2]>>16)*(cpuInfo[2]&0xff); }; void inline Fill3T(void *b, dword data, int len){ switch(len){ case 3: ((dword *)b)[2] = data; case 2: ((dword *)b)[1] = data; case 1: ((dword *)b)[0] = data; case 0: return; } __m128i q = _mm_set1_epi32(*(int*)&data); __m128i *w = (__m128i*)b; if(len >= 32) { __m128i *e = (__m128i*)b + (len>>2) - 8; if(len >= (cachesize>>2) && ((uintptr_t)w & 3) == 0) { // for really huge data, bypass the cache _mm_storeu_si128(w, q); // Head align int s=(-((int)((uintptr_t)b)>>2))&0x3; w = (__m128i*) ((dword*)b) + s; do { _mm_stream_si128(w++, q); _mm_stream_si128(w++, q); _mm_stream_si128(w++, q); _mm_stream_si128(w++, q); _mm_stream_si128(w++, q); _mm_stream_si128(w++, q); _mm_stream_si128(w++, q); _mm_stream_si128(w++, q); }while(w<=e); _mm_sfence(); } else do { _mm_storeu_si128(w++, q); _mm_storeu_si128(w++, q); _mm_storeu_si128(w++, q); _mm_storeu_si128(w++, q); _mm_storeu_si128(w++, q); _mm_storeu_si128(w++, q); _mm_storeu_si128(w++, q); _mm_storeu_si128(w++, q); }while(w<=e); } if(len & 16) { _mm_storeu_si128(w++, q); _mm_storeu_si128(w++, q); _mm_storeu_si128(w++, q); _mm_storeu_si128(w++, q); } if(len & 8) { _mm_storeu_si128(w++, q); _mm_storeu_si128(w++, q); } if(len & 4) { _mm_storeu_si128(w, q); } _mm_storeu_si128((__m128i*) (((dword*)b) + len - 4), q); // Tail align } Best regards, Tom
Tom1 wrote on Mon, 18 May 2020 20:57 Hi, My CPU here is Intel(R) Core(TM) i7-4790K: https://ark.intel.com/content/www/us/en/ark/products/80807/i ntel-core-i7-4790k-processor-8m-cache-up-to-4-40-ghz.html Not surprisingly, they say it has an 8M 'smart cache'. Please find attached two CSV files portraying execution time in ns for each call in average. The length is in dwords. Fill3a is there for reference and Fill3T is using 64 dword threshold for streaming in one and 2M dword (8MB) threshold in the other file. While not portrayed here, increasing the threshold above 32MB decreases the performance from 1.5 ms to 3.6 ms for a 32 MB buffer. Best regards, Tom If I interpret these numbers correctly, it looks like around 4MB potential drop because of cache bypass starts to be diminish, right? Thing is, I am afraid that making this dynamic will cause a lot of problems, starting with perfromance - it is after all another read from the memory. I would settle for some compromise constant there. Like 4MB... Mirek
What about this: never_inline void HugeFill(dword *t, dword c, int len) { __m128i val4 = _mm_set1_epi32(*(int*)&c); auto Set4S = [&](int at) { _mm_stream_si128((__m128i *)(t + at), val4); }; while((uintptr_t)t & 15) { // align to 16 bytes for SSE *t++ = c; len--; } while(len >= 16) { Set4S(0); Set4S(4); Set4S(8); Set4S(12); t += 16; len -= 16; } while(len--) *t++ = c; _mm_sfence(); } void Fill6(dword *t, dword c, int len) { if(len >= 4) { __m128i val4 = _mm_set1_epi32(*(int*)&c); auto Set4 = [&](int at) { _mm_storeu_si128((__m128i *)(t + at), val4); }; if(len > 4*1024*1024 / 4) { HugeFill(t, c, len); return; } while(len >= 16) { Set4(0); Set4(4); Set4(8); Set4(12); t += 16; len -= 16; } if(len & 8) { Set4(0); Set4(4); t += 8; } if(len & 4) { Set4(0); t += 4; } } if(len & 3) t[0] = t[(len & 2) >> 1] = t[(len & 2) & ((len & 1) << 1)] = c; }
Hi, Fill6 fails integrity check due to a small indexing glitch here: if(len & 8) { Set4(0); Set4(8); // << Should be 4 t += 8; } However, Fill3T is still faster below 64 and mostly on par above that on my i7. And thanks! I do indeed enjoy the final alignment trick! Very clever! Best regards, Tom
Yeah, there was another bug in it, I should test more before posting. In retrospective, while the trick is nice, I do not think it is worth it. But if you wanted to experiment with this path, I have found the way how to extend / simplify this. The basic idea is int nlen = -len; t[1 & HIBYTE(nlen)] = c; nlen++; t[2 & HIBYTE(nlen)] = c; nlen++; t[3 & HIBYTE(nlen)] = c; .... (at some point, nlen will become > 0 and thus HIBYTE goes from 0xff to 0x00, thus "grounding" indices). Also, I would like to try to explain why I am trying to beat Fill3T. It is about those switches, while switch(len) { case 0: case 1: case 2: default: } looks magnificent, it is actually 2 "unstable" branch predictions and quite a bit of code to compute the target address. So if(len & 2) { } if(len & 1) { } should be on par - 2 branch predictions and maybe a bit less of code.... Mirek
Also, a little note about your testing code: You loop over the same "len" many times and measure that. The problem is that first pass setups branch prediction so all other passes are predicted. If "len" is changing, prediction fails and you might get different results.... Which explains why my tests, which feeds random lens, shows a bit different picture... All in all, I think in the end we will just need to test this with Painter.... Mirek
Three more variants, based on your FillT. Fill7 is basically identical, with a little trick added (hope you like it). Fill7a has different "frontend". Fill8 is not performing very well, adding that just so that you know I have tested that variant too... Fill7 and Fill7a seem to be basically equal and maybe just a tiny bit faster than Fill3T.... void Fill7(dword *t, dword data, int len){ switch(len) { case 3: t[2] = data; case 2: t[1] = data; case 1: t[0] = data; case 0: return; } __m128i val4 = _mm_set1_epi32(data); auto Set4 = [&](int at) { _mm_storeu_si128((__m128i *)(t + at), val4); }; Set4(len - 4); // fill tail if(len >= 32) { if(len >= 1024*1024) { // for really huge data, bypass the cache HugeFill(t, data, len); return; } const dword *e = t + len - 32; do { Set4(0); Set4(4); Set4(8); Set4(12); Set4(16); Set4(20); Set4(24); Set4(28); t += 32; } while(t <= e); } if(len & 16) { Set4(0); Set4(4); Set4(8); Set4(12); t += 16; } if(len & 8) { Set4(0); Set4(4); t += 8; } if(len & 4) Set4(0); } void Fill7a(dword *t, dword data, int len){ if(len < 4) { if(len & 2) { t[0] = t[1] = data; t += 2; } if(len & 1) t[0] = data; return; } __m128i val4 = _mm_set1_epi32(data); auto Set4 = [&](int at) { _mm_storeu_si128((__m128i *)(t + at), val4); }; Set4(len - 4); // fill tail if(len >= 32) { if(len >= 1024*1024) { // for really huge data, bypass the cache HugeFill(t, data, len); return; } const dword *e = t + len - 32; do { Set4(0); Set4(4); Set4(8); Set4(12); Set4(16); Set4(20); Set4(24); Set4(28); t += 32; } while(t <= e); } if(len & 16) { Set4(0); Set4(4); Set4(8); Set4(12); t += 16; } if(len & 8) { Set4(0); Set4(4); t += 8; } if(len & 4) Set4(0); } void Fill8(dword *t, dword data, int len){ switch(len) { case 3: t[2] = data; case 2: t[1] = data; case 1: t[0] = data; case 0: return; } __m128i val4 = _mm_set1_epi32(data); auto Set4 = [&](int at) { _mm_storeu_si128((__m128i *)(t + at), val4); }; Set4(len - 4); // fill tail if(len >= 32) { if(len >= 1024*1024) { // for really huge data, bypass the cache HugeFill(t, data, len); return; } int cnt = len >> 5; do { Set4(0); Set4(4); Set4(8); Set4(12); len -= 32; Set4(16); Set4(20); Set4(24); Set4(28); t += 32; } while(len >= 32); } switch((len >> 2) & 7) { case 7: Set4(24); case 6: Set4(20); case 5: Set4(16); case 4: Set4(12); case 3: Set4(8); case 2: Set4(4); case 1: Set4(0); } }
mirek wrote on Tue, 19 May 2020 10:49 Also, a little note about your testing code: You loop over the same "len" many times and measure that. The problem is that first pass setups branch prediction so all other passes are predicted. If "len" is changing, prediction fails and you might get different results.... Which explains why my tests, which feeds random lens, shows a bit different picture... All in all, I think in the end we will just need to test this with Painter.... Mirek I wish I came to think of this benchmarking pitfall... I mean the branch prediction. Well, I agree that we need to put it in the BufferPainter environment for real test. Meanwhile, as you worked on 7, 7a and 8, I prepared 3T2, which avoids the switch and uses ifs instead. Funnily, your 7a does the same, but with table offsets. void inline Fill3T2(dword *b, dword data, int len){ if(len<4){ if(len&1) *b++ = data; if(len&2){ *b++ = data; *b++ = data; } return; } __m128i q = _mm_set1_epi32(*(int*)&data); __m128i *w = (__m128i*)b; if(len >= 32) { __m128i *e = (__m128i*)b + (len>>2) - 8; if(len > 4*1024*1024 / 4 && ((uintptr_t)w & 3) == 0) { // for really huge data, bypass the cache _mm_storeu_si128(w, q); // Head align int s=(-((int)((uintptr_t)b)>>2))&0x3; w = (__m128i*) (b + s); do { _mm_stream_si128(w++, q); _mm_stream_si128(w++, q); _mm_stream_si128(w++, q); _mm_stream_si128(w++, q); _mm_stream_si128(w++, q); _mm_stream_si128(w++, q); _mm_stream_si128(w++, q); _mm_stream_si128(w++, q); }while(w<=e); _mm_sfence(); } else do { _mm_storeu_si128(w++, q); _mm_storeu_si128(w++, q); _mm_storeu_si128(w++, q); _mm_storeu_si128(w++, q); _mm_storeu_si128(w++, q); _mm_storeu_si128(w++, q); _mm_storeu_si128(w++, q); _mm_storeu_si128(w++, q); }while(w<=e); } if(len & 16) { _mm_storeu_si128(w++, q); _mm_storeu_si128(w++, q); _mm_storeu_si128(w++, q); _mm_storeu_si128(w++, q); } if(len & 8) { _mm_storeu_si128(w++, q); _mm_storeu_si128(w++, q); } if(len & 4) { _mm_storeu_si128(w, q); } _mm_storeu_si128((__m128i*) (b + len - 4), q); // Tail align } I really like the w++ incremental pointer logic over the Set4(pointer+offset). This approach seems to give a small improvement on my system. Next, I will test your 7 + 7a and report against 3T2. But seriously, we need to put an end to this madness! The bang for the buck is rapidly decreasing as working hours are increasing... Best regards, Tom
[quote title=Tom1 wrote on Tue, 19 May 2020 12:35]mirek wrote on Tue, 19 May 2020 10:49 I really like the w++ incremental pointer logic over the Set4(pointer+offset). This approach seems to give a small improvement on my system. Compiler actually converts that to offsets anyway... (I have checked disassembly). Quote: But seriously, we need to put an end to this madness! The bang for the buck is rapidly decreasing as working hours are increasing... Well, you have started it Mirek
[quote title=mirek wrote on Tue, 19 May 2020 13:45]Tom1 wrote on Tue, 19 May 2020 12:35 mirek wrote on Tue, 19 May 2020 10:49 I really like the w++ incremental pointer logic over the Set4(pointer+offset). This approach seems to give a small improvement on my system. Compiler actually converts that to offsets anyway... (I have checked disassembly). Quote: But seriously, we need to put an end to this madness! The bang for the buck is rapidly decreasing as working hours are increasing... Well, you have started it Mirek I admit to it! My fault... Anyway, pick you choice: 7a or 3T2, but note that MSBT19 (32bit I mean) likes 3T2 better on short transfers. CLANG, CLANGx64 and MSBT19x64 are happy with both. (But, please do your own benchmarks, as this is just my repeated scan through different lengths with the pitfall you pointed out earlier.) Best regards, Tom
Hi, WARNING: Something still wrong in 3T2 alignment code. I will continue to investigate it. Best regards, Tom
Hi Mirek, Yes, I'm nuts... still working at this hour. Anyway, here's a new version - Fill3T3 - that can actually handle all alignment variations (even those not handled by 7a). Please benchmark and check for correctness: never_inline void FillStream(dword *b, dword data, int len){ while((uintptr_t)b & 15){ // Try to align *b++=data; len--; }; __m128i *w = (__m128i *)b; __m128i q = _mm_set1_epi32((int)data); if(len>=16){ __m128i *e = w + (len>>2) - 3; do{ _mm_stream_si128(w++, q); _mm_stream_si128(w++, q); _mm_stream_si128(w++, q); _mm_stream_si128(w++, q); }while(w<e); } if(len & 8) { _mm_stream_si128(w++, q); _mm_stream_si128(w++, q); } if(len & 4) { _mm_stream_si128(w++, q); } _mm_sfence(); _mm_storeu_si128((__m128i*)(b + len - 4), q); // Tail align } void inline Fill3T3(dword *b, dword data, int len){ if(len<4){ if(len&1) *b++ = data; if(len&2){ *b++ = data; *b++ = data; } return; } __m128i *w = (__m128i *)b; __m128i q = _mm_set1_epi32((int)data); if(len >= 32) { if(len>1024*1024 && (((uintptr_t)b & 3)==0)){ FillStream(b,data,len); return; } __m128i *e = w + (len>>2) - 7; do{ _mm_storeu_si128(w++, q); _mm_storeu_si128(w++, q); _mm_storeu_si128(w++, q); _mm_storeu_si128(w++, q); _mm_storeu_si128(w++, q); _mm_storeu_si128(w++, q); _mm_storeu_si128(w++, q); _mm_storeu_si128(w++, q); }while(w<e); } if(len & 16) { _mm_storeu_si128(w++, q); _mm_storeu_si128(w++, q); _mm_storeu_si128(w++, q); _mm_storeu_si128(w++, q); } if(len & 8) { _mm_storeu_si128(w++, q); _mm_storeu_si128(w++, q); } if(len & 4) { _mm_storeu_si128(w++, q); } _mm_storeu_si128((__m128i*)(b + len - 4), q); // Tail align } Best regards, Tom
[quote title=Tom1 wrote on Wed, 20 May 2020 01:34]Hi Mirek, Yes, I'm nuts... still working at this hour. Anyway, here's a new version - Fill3T3 - that can actually handle all alignment variations (even those not handled by 7a). Please benchmark and check for correctness: if(len & 8) { _mm_stream_si128(w++, q); _mm_stream_si128(w++, q); } if(len & 4) { _mm_stream_si128(w++, q); } Yeah, I think that after filling 8MB of data, this will really have impact compared to trivial loop Mirek
mirek wrote on Wed, 20 May 2020 02:52 Yeah, I think that after filling 8MB of data, this will really have impact compared to trivial loop Mirek Best regards, Tom
Hi, There must still be something wrong with 3T3 because applying it to BufferPainter (replacing FillRGBA) causes artifacts in drawing. E.g. PainterExamples spiral example at 3x scale clearly shows noise in line edges. Best regards, Tom
Tom1 wrote on Wed, 20 May 2020 10:04 Hi, There must still be something wrong with 3T3 because applying it to BufferPainter (replacing FillRGBA) causes artifacts in drawing. E.g. PainterExamples spiral example at 3x scale clearly shows noise in line edges. Best regards, Tom My guts feeling is either the tail fill, or less likely, "e" computation. I think these are simpler code in Fill7a.... (and actually, these are the only real difference now).
Hi, No, Sorry... I'll take that alarm back. There is no error in 3T3 after all. My copy of the code inside Painter was faulty... Now I took the correct version and it is all good now. I'm just too tired after not sleeping too much lately... Best regards, Tom
So I have replaced memsetd with Fill7a, replaced RGBA fill with (new) memsetd and did benchmarks. Except the situation where the benchmark involves Clear of large area, numbers have not changed... EDIT: Bug on my part, retesting... Mirek
OK, after retesting, I think it might be at most 3% faster. Looking at fillers, I think there is much more time spent in AlphaBlend function - even if it is just for segment start/end pixels. Perhaps that one should be SSE2 optimized? Mirek
Hi Mirek, Two things to consider before you go with 7a: - 7a crashes on unaligned buffers (t&3) while 3T3 handles them all. - 3T3 is faster on MSBT19 with short transfers up to 50-60 dwords. Best regards, Tom
mirek wrote on Wed, 20 May 2020 13:23 OK, after retesting, I think it might be at most 3% faster. Looking at fillers, I think there is much more time spent in AlphaBlend function - even if it is just for segment start/end pixels. Perhaps that one should be SSE2 optimized? Mirek Hi, My SSE2 battery is now 'discharged' for a while.... Need to recharge before next use. I also did some testing on span filler with memcpy. This is based on using IMAGE_OPAQUE of the image being rendered. It does improve the speed somewhat, but the edges cause a problem since the edge is alpha blended even if FILL_FAST is specified. So, this needs some reconsideration and better knowledge on the Painter internals (i.e. beyond my level...): BufferPainter.h: struct SpanSource { int kind; SpanSource(){ kind = IMAGE_OPAQUE; } virtual void Get(RGBA *span, int x, int y, unsigned len) = 0; virtual ~SpanSource() {} }; Fillers.cpp: void SpanFiller::Render(int val, int len) { if(val == 0) { t += len; s += len; return; } if(alpha != 256) val = alpha * val >> 8; if(val == 256) { if(ss->kind==IMAGE_OPAQUE) memcpy(t,s,len*sizeof(RGBA)); // apex_memcpy() would be even faster else{ for(int i = 0; i < len; i++) { if(s[i].a == 255) t[i] = s[i]; else AlphaBlend(t[i], s[i]); } } t += len; s += len; } else { const RGBA *e = t + len; while(t < e) AlphaBlendCover8(*t++, *s++, val); } } Painter/Image.cpp: struct PainterImageSpan : SpanSource, PainterImageSpanData { LinearInterpolator interpolator; PainterImageSpan(const PainterImageSpanData& f) : PainterImageSpanData(f) { interpolator.Set(xform); kind = image.GetKindNoScan(); // Add this } Best regards, Tom
I was aware about unaligned problem, thats fixed in final version. That said, unaligned in general should be considered illegal anyway, because otherwise hell will broke lose with Armv6....
Quote: I was aware about unaligned problem, thats fixed in final version. That said, unaligned in general should be considered illegal anyway, because otherwise hell will broke lose with Armv6.... But that's good to know. In this case we could drop (t&3) code entirely from 3T3 and improve instruction cache locality for even better results on short transfers. ((Is there a way to 'cleanly crash' (whatever that might mean) an application attempting unaligned memset? Now it just disappears from the process list at least on Windows.)) EDIT: Let me rephrase it: Is there a way to check during development that an application will never use unaligned memset? Best regards, Tom
Tom1 wrote on Wed, 20 May 2020 13:01 EDIT: Let me rephrase it: Is there a way to check during development that an application will never use unaligned memset? memsetd! Yes, put ASSERT(((uintptr_t)t & 3) == 0); to memsetd Mirek
Hi, This is strange, since I immediately added the inline to 7a when I started testing it. (I found out earlier that MSBT19 did not do it for me.) Now I did a new run and the result is in the attached csv. Can you post the latest 7a if it is any different compared to the one posted here above? Best regards, Tom
Tom1 wrote on Wed, 20 May 2020 16:15 Hi, This is strange, since I immediately added the inline to 7a when I started testing it. (I found out earlier that MSBT19 did not do it for me.) Now I did a new run and the result is in the attached csv. Can you post the latest 7a if it is any different compared to the one posted here above? Best regards, Tom It is now in trunk as memsetd.... Mirek
I am getting quite different picture: int bsize=8*1024*1024; Buffer<dword> b(bsize, 0); dword cw = 123; String result="\"N\",\"memsetd()\",\"Fill3T3()\"\r\n"; for(int len=1;len<=bsize;){ int maximum=100000000/len; int64 t0=usecs(); for(int i = 0; i < maximum; i++) memsetd(~b, cw, len); int64 t1=usecs(); for(int i = 0; i < maximum; i++) Fill3T3(~b, cw, len); int64 t2=usecs(); String r = Format("%d,%f,%f",len,1000.0*(t1-t0)/maximum,1000.0*(t2-t1)/maximum); RLOG(r); result.Cat(r + "\r\n"); if(len<64) len++; else len*=2; } SaveFile(GetHomeDirFile("memset.csv"),result); I am starting to wonder if there is difference between our MSC 32bit compilers...
Ha, funny. It depends on order of functions tested. If I test memsetd second, I am getting different numbers
mirek wrote on Wed, 20 May 2020 18:31 I am getting quite different picture: int bsize=8*1024*1024; Buffer<dword> b(bsize, 0); dword cw = 123; String result="\"N\",\"memsetd()\",\"Fill3T3()\"\r\n"; for(int len=1;len<=bsize;){ int maximum=100000000/len; int64 t0=usecs(); for(int i = 0; i < maximum; i++) memsetd(~b, cw, len); int64 t1=usecs(); for(int i = 0; i < maximum; i++) Fill3T3(~b, cw, len); int64 t2=usecs(); String r = Format("%d,%f,%f",len,1000.0*(t1-t0)/maximum,1000.0*(t2-t1)/maximum); RLOG(r); result.Cat(r + "\r\n"); if(len<64) len++; else len*=2; } SaveFile(GetHomeDirFile("memset.csv"),result); I am starting to wonder if there is difference between our MSC 32bit compilers... Hi, No wonder we ended up with (very slightly) different approach... Your results are more or less reversed to what I'm getting. I tried to reorder the calls too, but without any observable difference. It's either the different CPUs or a different compiler. My compiler is: Microsoft (R) C/C++ Optimizing Compiler Version 19.21.27702.2 for x86 Copyright (C) Microsoft Corporation. All rights reserved. Should I downgrade or upgrade?... Anyway, seriously I'm pleased with the final result here. The filler is now better than anything before and can be used generally for all clearing/presetting of buffers. I use this a lot in signal processing in addition to clearing the ImageBuffer for BufferPainter. After all, the ImageBuffer needs to be cleared or preset to user preference background color once before each display update. It is much better to have a 1.5 ms delay instead of 3.6 ms delay before drawing approximately 10-20 ms worth of vector map data on the screen. Should this new memsetd() now be deployed all over the u++? I mean e.g. Core/Topt.h :: Fill? Thank you a lot for your great work on this! Best regards, Tom
[quote title=Tom1 wrote on Wed, 20 May 2020 19:51]mirek wrote on Wed, 20 May 2020 18:31 Should this new memsetd() now be deployed all over the u++? I mean e.g. Core/Topt.h :: Fill? IDK, maybe as specialisation... Mirek
OK, so I could not stop digging and found last important ingredient: alignment matters! void FillX(void *p, dword data, int len) { dword *t = (dword *)p; if(len < 4) { if(len & 2) { t[0] = t[1] = t[len - 1] = data; return; } if(len & 1) t[0] = data; return; } __m128i val4 = _mm_set1_epi32(data); auto Set4 = [&](int at) { _mm_storeu_si128((__m128i *)(t + at), val4); }; Set4(len - 4); // fill tail if(len >= 16) { Set4(0); // align up on 16 bytes boundary const dword *e = t + len; t = (dword *)(((uintptr_t)t | 15) + 1); len = e - t; e -= 16; if(len >= 1024*1024) { // for really huge data, bypass the cache huge_memsetd(t, data, len); return; } while(t <= e) { Set4(0); Set4(4); Set4(8); Set4(12); t += 16; } } if(len & 8) { Set4(0); Set4(4); t += 8; } if(len & 4) Set4(0); } This is about twice as fast as Fill7a for len > 60 (up to cache bypass limit).
mirek wrote on Wed, 20 May 2020 16:18 Tom1 wrote on Wed, 20 May 2020 13:01 EDIT: Let me rephrase it: Is there a way to check during development that an application will never use unaligned memset? memsetd! Yes, put ASSERT(((uintptr_t)t & 3) == 0); to memsetd Mirek Good point! Please do! Best regards, Tom
Hi, This new FillX is incredibly elegant! Congratulations Mirek! I really do like your new findings there. You just need to rename it as memsetd() and place in the correct header in Core... Best regards, Tom
Thank you all for your job. Although please review this in Redmine.
Hi Koldo, I checked and #include <emmintrin.h> seems to work just fine for what we are working on. Thanks for pointing this out. Mirek: Agree? Best regards, Tom
Mirek, I just found that there is a sweet spot at ~0x3f alignment (i.e. 64 bytes) on my CPU. This is presumably the L1 cache line length, if I'm not mistaken. Best regards, Tom EDIT: It just looks that I cannot squeeze the benefit out as re-alignment code tends to eat what would could possibly be achieved here. However, if allocator could allocate large blocks at even 64 byte limits, that could improve performance behind the scenes.
Hello mirek ans Tom, Grenat work hère but I have une simple question: what is the point with cache ? Normally cache speeds things up when you need to reaccess data just After writing it. So filling a buffer with a constant value that is not read immediatly After in most cases isn't a corresponding use case. So, I think that having a fill function that doesn't use cache at all will benefit in two points: Timing stability and more importantly, cache is not touched so it can speed up other functions calls further
Didier wrote on Fri, 22 May 2020 09:32 Hello mirek ans Tom, Grenat work hère but I have une simple question: what is the point with cache ? Normally cache speeds things up when you need to reaccess data just After writing it. So filling a buffer with a constant value that is not read immediatly After in most cases isn't a corresponding use case. So, I think that having a fill function that doesn't use cache at all will benefit in two points: Timing stability and more importantly, cache is not touched so it can speed up other functions calls further Thing that started this whole issue: If you need to clear buffer for 4K screen, that is about 32MB of data. Thats definitely more than can fit into the cache. So what really happens in that in this case is that at some point cache runs out and you are significantly slowed down by CPU writing data from the cache to main memory. The "fix" is to bypass the cache in this case (we have for now established that the reasonable threshold is somewhere around 4MB). That said, really a lot of other things were optimised thereafter, mostly on the other size of size spectrum...
Tom1 wrote on Thu, 21 May 2020 19:25 EDIT: It just looks that I cannot squeeze the benefit out as re-alignment code tends to eat what would could possibly be achieved here. However, if allocator could allocate large blocks at even 64 byte limits, that could improve performance behind the scenes. It cannot as alignment is important part of block information... Mirek
So I have implemented a bunch of other functions based on info gathered during this session: memcpyd svo_memset svo_memcpy Now I have hopefully the last problem to tune... I have tried to put svo_memcpy to Vector::Add grow routine and it indeed improved performance a bit. Then tried to improve this even more and put memcpyd (which svo_memcpy is using as backend in some situations) and performance dropped. I believe that the problem is that memcpyd became too fat and it screws inlining. So the thing to solve now is to find how to remove some if this fat to non-inline.... (svo_memcpy already has such non-inlined part). Probably same should happend to memsetd too....
One question. To use these new features, is it necessary to set compiler flags, like /arch:AVX in Visual Studio?
Quote: I believe that the problem is that memcpyd became too fat and it screws inlining. So the thing to solve now is to find how to remove some if this fat to non-inline.... (svo_memcpy already has such non-inlined part). Probably same should happend to memsetd too.... Hi Mirek, I think this could be the same phenomenon that caused me issues with 32-bit MSC. It was more critical to code length and the short transfers suffered immediately when code size increased. At the same time MSBT19x64 and both CLANG and CLANGx64 did not experience any trouble. Perhaps MSBT19 did not do as good job with code size as the rest and on my CPU the instruction cache was exhausted. I bet the instruction cache on your CPU is larger than what my i7 has. At some moment I was thinking of offering the functions as two variants: inline and never_inline, in a way that the never_inline is simply calling the inline. An then when the code benefits from it, calling the never_inline variant. Then I also thought of handling something like <= 16 .. 32 sizes inline and the rest in a deeper never_inline function. This would probably improve the situation without adding so much complexity. Best regards, Tom
koldo wrote on Fri, 22 May 2020 10:29 One question. To use these new features, is it necessary to set compiler flags, like /arch:AVX in Visual Studio? No so far. This is just SSE2, which is enabled by default for ages now... Of course, the next logical step is to use AVX256 Mirek
koldo wrote on Fri, 22 May 2020 11:29 One question. To use these new features, is it necessary to set compiler flags, like /arch:AVX in Visual Studio? Hi Koldo, Here I do not need /arch:AVX or any other compiler flag added. It's just that include (#include <smmintrin.h> or #include <emmintrin.h>, which works for me, I think. Best regards, Tom EDIT: Mirek was faster to respond!
[quote title=Tom1 wrote on Fri, 22 May 2020 11:13]Quote: Then I also thought of handling something like <= 16 .. 32 sizes inline and the rest in a deeper never_inline function. This would probably improve the situation without adding so much complexity. In the trunk now... >=16 now handled by non-inline function. There is impact in your benchmark (the one that runs for all sizes), less impact in my benchmark (with ransom sizes), but I think this is the right move... Another benefit is that we can now consider using AVX (testing for AVX presence would be clumsy in inline function I think). Mirek
[quote title=mirek wrote on Fri, 22 May 2020 12:39]Tom1 wrote on Fri, 22 May 2020 11:13 Quote: Then I also thought of handling something like <= 16 .. 32 sizes inline and the rest in a deeper never_inline function. This would probably improve the situation without adding so much complexity. In the trunk now... >=16 now handled by non-inline function. There is impact in your benchmark (the one that runs for all sizes), less impact in my benchmark (with ransom sizes), but I think this is the right move... Another benefit is that we can now consider using AVX (testing for AVX presence would be clumsy in inline function I think). Mirek The apex_memmove() did the architecture checking on startup (or first run) and then initialized function pointers to optimal versions. I think we could do this too in some INITBLOCK. Best regards, Tom
mirek wrote on Fri, 22 May 2020 12:39 In the trunk now... >=16 now handled by non-inline function. There is impact in your benchmark (the one that runs for all sizes), less impact in my benchmark (with ransom sizes), but I think this is the right move... It looks like >32 might be better in this case... Not sure though. BR, Tom
Dear colleagues Please consider Sender proposal: - Remove #include <emmintrin.h> from Blit.h - Include #include <immintrin.h> in config.h As now the intrinsics are included inside Upp namespace, they cannot be used later by Eigen. config.h is included in Core.h before Upp namespace. Thank you!
Tom1 wrote on Fri, 22 May 2020 11:59 mirek wrote on Fri, 22 May 2020 12:39 In the trunk now... >=16 now handled by non-inline function. There is impact in your benchmark (the one that runs for all sizes), less impact in my benchmark (with ransom sizes), but I think this is the right move... It looks like >32 might be better in this case... Not sure though. BR, Tom It in turn makes inlined part bigger.... I would rather be careful there. OK, for what is worth, I have tried with AVX and I do not see any improvement. Here is the code (for CLANG): __attribute__((target ("avx"))) never_inline void memsetd_l2(dword *t, dword data, size_t len) { __m128i val4 = _mm_set1_epi32(data); __m256i val8 = _mm256_set1_epi32(data); auto Set4 = [&](size_t at) { _mm_storeu_si128((__m128i *)(t + at), val4); }; #define Set8(at) _mm256_storeu_si256((__m256i *)(t + at), val8); Set4(len - 4); // fill tail if(len >= 32) { if(len >= 1024*1024) { // for really huge data, bypass the cache huge_memsetd(t, data, len); return; } Set8(0); // align up on 16 bytes boundary const dword *e = t + len; t = (dword *)(((uintptr_t)t | 31) + 1); len = e - t; e -= 32; while(t <= e) { Set8(0); Set8(8); Set8(16); Set8(24); t += 32; } } if(len & 16) { Set8(0); Set8(8); t += 16; } if(len & 8) { Set8(0); t += 8; } if(len & 4) Set4(0); } inline void FillX(void *p, dword data, size_t len) { dword *t = (dword *)p; if(len < 4) { if(len & 2) { t[0] = t[1] = t[len - 1] = data; return; } if(len & 1) t[0] = data; return; } if(len >= 16) { memsetd_l2(t, data, len); return; } __m128i val4 = _mm_set1_epi32(data); auto Set4 = [&](size_t at) { _mm_storeu_si128((__m128i *)(t + at), val4); }; Set4(len - 4); // fill tail if(len & 8) { Set4(0); Set4(4); t += 8; } if(len & 4) Set4(0); } Frankly I am sort of happy, because GCC/CLANG way of dealing with AVX is really stupid: It declines AVX instrinics, unless you compile whole function for AVX code, but then it starts generating AVX opcodes everywhere and the funciton does not run on non-AVX CPUs anymore.
Quote: I have tried with AVX and I do not see any improvement. So, this means SSE2 is enough to saturate the memory bus completely. Thanks also for the new memcpy optimizations. This is equally important in many areas. Best regards, Tom
Added memcpy optimized for sizeof 8 and 16 and this little neat function to make sense from it all: template <class T> void memcpy_t(T *t, const T *s, size_t count) { if((sizeof(T) & 15) == 0) memcpydq((dqword *)t, (const dqword *)s, count * (sizeof(T) >> 4)); else if((sizeof(T) & 7) == 0) memcpyq((qword *)t, (const qword *)s, count * (sizeof(T) >> 3)); else if((sizeof(T) & 3) == 0) memcpyd((dword *)t, (const dword *)s, count * (sizeof(T) >> 2)); else svo_memcpy((void *)t, (void *)s, count * sizeof(T)); } Vector<String>::ReAlloc(int newalloc) disassembly now looks magnificent, copying elements to new buffer with SSE2...
I have the first implementation and test of SSE2 AlphaBlend: TIMING SSE : 46.95 ms - 46.95 ns (58.00 ms / 1000000 ), min: 0.00 ns, max: 1.00 ms, nesting: 0 - 1000000 TIMING Non SSE : 123.95 ms - 123.95 ns (135.00 ms / 1000000 ), min: 0.00 ns, max: 1.00 ms, nesting: 0 - 1000000
Hello Mirek, On Linux 5.4 and 5.6, with CLANG 10.0 TIMING SSE : 119.41 ms - 119.41 ns ( 1.06 s / 1000000 ), min: 0.00 ns, max: 1.00 ms, nesting: 0 - 1000000 TIMING Non SSE : 232.41 ms - 232.41 ns ( 1.18 s / 1000000 ), min: 0.00 ns, max: 1.00 ms, nesting: 0 - 1000000 On GCC (10.1): apparently _mm_storeu_si32 is yet to be implemented. : '_mm_storeu_si32' was not declared in this scope; did you mean '_mm_storeu_epi32'? (): 47 | _mm_storeu_si32(rgba, PackRGBA(x, _mm_setzero_si128())); (): | ^~~~~~~~~~~~~~~ (): | _mm_storeu_epi32 Possible workaround is given here: https://stackoverflow.com/questions/58063933/how-can-a-sse2- function-be-missing-from-the-header-it-is-supposed-to-be-in Best regards, Oblivion
Hi! Sorry for the delay... I was out of town for a while. Here are my results for Windows 10 pro x64 on Core i7: MSBT19x64: TIMING SSE : 37.08 ms - 37.08 ns (50.00 ms / 1000000 ), min: 0.00 ns, max: 1.00 ms, nesting: 0 - 1000000 TIMING Non SSE : 129.08 ms - 129.08 ns (142.00 ms / 1000000 ), min: 0.00 ns, max: 1.00 ms, nesting: 0 - 1000000 MSBT19: TIMING SSE : 29.88 ms - 29.88 ns (45.00 ms / 1000000 ), min: 0.00 ns, max: 1.00 ms, nesting: 0 - 1000000 TIMING Non SSE : 125.88 ms - 125.88 ns (141.00 ms / 1000000 ), min: 0.00 ns, max: 1.00 ms, nesting: 0 - 1000000 CLANG: TIMING SSE : 37.41 ms - 37.41 ns (50.00 ms / 1000000 ), min: 0.00 ns, max: 2.00 ms, nesting: 0 - 1000000 TIMING Non SSE : 125.41 ms - 125.41 ns (138.00 ms / 1000000 ), min: 0.00 ns, max: 1.00 ms, nesting: 0 - 1000000 CLANGx64: TIMING SSE : 37.43 ms - 37.43 ns (47.00 ms / 1000000 ), min: 0.00 ns, max: 1.00 ms, nesting: 0 - 1000000 TIMING Non SSE : 129.43 ms - 129.43 ns (139.00 ms / 1000000 ), min: 0.00 ns, max: 1.00 ms, nesting: 0 - 1000000 Impressive numbers Mirek! When is this going to be available on BufferPainter? Best regards, Tom
Tom1 wrote on Tue, 26 May 2020 13:14 Hi! Sorry for the delay... I was out of town for a while. Here are my results for Windows 10 pro x64 on Core i7: MSBT19x64: TIMING SSE : 37.08 ms - 37.08 ns (50.00 ms / 1000000 ), min: 0.00 ns, max: 1.00 ms, nesting: 0 - 1000000 TIMING Non SSE : 129.08 ms - 129.08 ns (142.00 ms / 1000000 ), min: 0.00 ns, max: 1.00 ms, nesting: 0 - 1000000 MSBT19: TIMING SSE : 29.88 ms - 29.88 ns (45.00 ms / 1000000 ), min: 0.00 ns, max: 1.00 ms, nesting: 0 - 1000000 TIMING Non SSE : 125.88 ms - 125.88 ns (141.00 ms / 1000000 ), min: 0.00 ns, max: 1.00 ms, nesting: 0 - 1000000 CLANG: TIMING SSE : 37.41 ms - 37.41 ns (50.00 ms / 1000000 ), min: 0.00 ns, max: 2.00 ms, nesting: 0 - 1000000 TIMING Non SSE : 125.41 ms - 125.41 ns (138.00 ms / 1000000 ), min: 0.00 ns, max: 1.00 ms, nesting: 0 - 1000000 CLANGx64: TIMING SSE : 37.43 ms - 37.43 ns (47.00 ms / 1000000 ), min: 0.00 ns, max: 1.00 ms, nesting: 0 - 1000000 TIMING Non SSE : 129.43 ms - 129.43 ns (139.00 ms / 1000000 ), min: 0.00 ns, max: 1.00 ms, nesting: 0 - 1000000 Impressive numbers Mirek! When is this going to be available on BufferPainter? Best regards, Tom I guess by the end of the week. Still fixing bugs + there is like 8 variants to implement...
While optimizing memcpy and memset, I have tried a new look at othre things, like String comparison and memhash. I think I improved String::operator== a tiny bit and now I am working on memhash function. Decided to introduce "hash_t" and to have hash value 64 bit when CPU_64. After bit of experimenting, I have found these functions (one for 64 bit, other 32 bit) work best: never_inline uint64 memhash64(const void *ptr, int len) { const byte *s = (byte *)ptr; uint64 val = HASH64_CONST1; if(len >= 8) { if(len >= 32) { uint64 val1, val2, val3, val4; val1 = val2 = val3 = val4 = HASH64_CONST1; while(len >= 32) { val1 = HASH64_CONST2 * val1 + *(qword *)(s); val2 = HASH64_CONST2 * val2 + *(qword *)(s + 8); val3 = HASH64_CONST2 * val3 + *(qword *)(s + 16); val4 = HASH64_CONST2 * val4 + *(qword *)(s + 24); s += 32; len -= 32; } val = HASH64_CONST2 * val + val1; val = HASH64_CONST2 * val + val2; val = HASH64_CONST2 * val + val3; val = HASH64_CONST2 * val + val4; } const byte *e = s + len - 8; while(s < e) { val = HASH64_CONST2 * val + *(qword *)(s); s += 8; } return HASH64_CONST2 * val + *(qword *)(e); } if(len > 4) { val = HASH64_CONST2 * val + *(dword *)(s); val = HASH64_CONST2 * val + *(dword *)(s + len - 4); return val; } if(len >= 2) { val = HASH64_CONST2 * val + *(word *)(s); val = HASH64_CONST2 * val + *(word *)(s + len - 2); return val; } return len ? HASH64_CONST2 * val + *s : val; } never_inline uint64 memhash32(const void *ptr, int len) { const byte *s = (byte *)ptr; uint64 val = HASH32_CONST1; if(len >= 4) { if(len >= 16) { uint64 val1, val2, val3, val4; val1 = val2 = val3 = val4 = HASH32_CONST1; while(len >= 32) { val1 = HASH32_CONST2 * val1 + *(dword *)(s); val2 = HASH32_CONST2 * val2 + *(dword *)(s + 4); val3 = HASH32_CONST2 * val3 + *(dword *)(s + 8); val4 = HASH32_CONST2 * val4 + *(dword *)(s + 12); s += 16; len -= 16; } val = HASH32_CONST2 * val + val1; val = HASH32_CONST2 * val + val2; val = HASH32_CONST2 * val + val3; val = HASH32_CONST2 * val + val4; } const byte *e = s + len - 4; while(s < e) { val = HASH32_CONST2 * val + *(dword *)(s); s += 4; } return HASH32_CONST2 * val + *(dword *)(e); } if(len >= 2) { val = HASH32_CONST2 * val + *(word *)(s); val = HASH32_CONST2 * val + *(word *)(s + len - 2); return val; } return len ? HASH32_CONST2 * val + *s : val; } While other "mem*" functions are easy to write tests for, hasing is a bit more complicated; can I request some code review here? Basically, I think combination functions are OK, but I would like to be sure it reads exactly len bytes from memory (it is ok if some are read twice...). Mirek