-
Content Count
3488 -
Joined
-
Last visited
-
Days Won
171
Everything posted by David Heffernan
-
I'm still seeing an AV here even with that change. It would be really nice to get this fixed and then I can update my benchmark program again.
-
UPDATED BENCHMARK: {$APPTYPE CONSOLE} uses System.SysUtils, System.Classes, System.Diagnostics; //******************************************** // Constants to tune the benchmark performance const HexStringLength = 64; InputDataCount = 512; IterationCount = 20000; //***************************************************************** // David Heffernan's routine, with Move replace by Int64 assignment {$DEFINE ReplaceMoveWithInt64Assign} function HexToBin(const HexValue: string): string; const BinaryValues: array [0..15] of string = ( '0000', '0001', '0010', '0011', '0100', '0101', '0110', '0111', '1000', '1001', '1010', '1011', '1100', '1101', '1110', '1111' ); var HexDigit: Char; HexDigitValue: Integer; Ptr: PChar; begin SetLength(Result, Length(HexValue) * 4); Ptr := Pointer(Result); for HexDigit in HexValue do begin case HexDigit of '0'..'9': HexDigitValue := Ord(HexDigit) - Ord('0'); 'a'..'f': HexDigitValue := 10 + Ord(HexDigit) - Ord('a'); 'A'..'F': HexDigitValue := 10 + Ord(HexDigit) - Ord('A'); else raise EConvertError.CreateFmt('Invalid hex digit ''%s'' found in ''%s''', [HexDigit, HexValue]); end; {$IFDEF ReplaceMoveWithInt64Assign} PInt64(Ptr)^ := PInt64(BinaryValues[HexDigitValue])^; {$ELSE} Move(Pointer(BinaryValues[HexDigitValue])^, Ptr^, 4 * SizeOf(Char)); {$ENDIF} Inc(Ptr, 4); end; end; //*********************** // Kas Ob's asm32 version procedure CharToBin_ASM32(HexChar: Char; HexBuffer: PChar); asm push edi mov edi,edx // Get the decimal value of one Hex Char (= half byte) movzx eax, HexChar mov ecx, 57 sub ecx, eax sar ecx, 31 and ecx, 39 neg ecx add eax, ecx add eax, - 48 // Produce 4 Chars presenting 4 bits of HexChar xor ecx,ecx mov dx,$1 test al,4 cmovne cx,dx shl ecx,16 test al,8 cmovne cx,dx add ecx,$00300030 mov [edi],ecx xor ecx,ecx test al,1 cmovne cx,dx shl ecx,16 test al,2 cmovne cx,dx add ecx,$00300030 mov [edi+4],ecx pop edi end; function HexToBinAsm32(const HexValue: string): string; var HexDigit: Char; Ptr: PChar; begin SetLength(Result, Length(HexValue) * 4); Ptr := Pointer(Result); for HexDigit in HexValue do begin case HexDigit of '0'..'9','a'..'f','A'..'F': CharToBin_ASM32(HexDigit, Ptr); else raise EConvertError.CreateFmt('Invalid hex digit ''%s'' found in ''%s''', [HexDigit, HexValue]); end; Inc(Ptr, 4); end; end; //********************* // Kas Ob's xmm version procedure CharToBin_XMM(HexChar: Char; HexBuffer: PChar); const DEC_TO_BIN_WORD_MASK: array[0..7] of UInt16 = ($01, $02,$00,$00, $04, $08, $00, $00); DEC_TO_BIN_FF_TO_CHARONE_DISTANCE: array[0..7] of UInt16 = ($FFCF, $FFCF, $FFCF, $FFCF, $FFCF, $FFCF, $FFCF, $FFCF); DEC_TO_BIN_REVERSE_MASK: array[0..15] of Byte = (10, $80, 8, $80, 2, $80, 0, $80, $80, $80, $80, $80, $80, $80, $80, $80); asm movzx eax, HexChar mov ecx, 57 sub ecx, eax sar ecx, 31 and ecx, 39 neg ecx add eax, ecx add eax, - 48 // Produce 4 Chars presenting 4 bits of HexChar movd xmm0, eax pxor xmm1, xmm1 movdqu xmm2, DEC_TO_BIN_FF_TO_CHARONE_DISTANCE punpckldq xmm0, xmm0 packssdw xmm0, xmm0 pand xmm0, dqword ptr[DEC_TO_BIN_WORD_MASK] pcmpeqw xmm0, xmm1 psubw xmm0, xmm2 movdqu xmm3,DEC_TO_BIN_REVERSE_MASK PSHUFB xmm0, xmm3 // reverse the result movq qword ptr[HexBuffer], xmm0 end; function HexToBinXmm(const HexValue: string): string; var HexDigit: Char; Ptr: PChar; begin SetLength(Result, Length(HexValue) * 4); Ptr := Pointer(Result); for HexDigit in HexValue do begin case HexDigit of '0'..'9','a'..'f','A'..'F': CharToBin_XMM(HexDigit, Ptr); else raise EConvertError.CreateFmt('Invalid hex digit ''%s'' found in ''%s''', [HexDigit, HexValue]); end; Inc(Ptr, 4); end; end; //*************** // Benchmark code function RandomHexDigit: Char; var Ordinal: Integer; begin Ordinal := Random(16); case Ordinal of 0..9: Result := Chr(Ord('0') + Ordinal); 10..15: Result := Chr(Ord('a') + Ordinal - 10); else raise Exception.Create(''); end; end; function RandomHexString(Length: Integer): string; var Index: Integer; begin SetLength(Result, Length); for Index := 1 to Length do Result[Index] := RandomHexDigit; end; procedure Benchmark; var Index, Iteration: Integer; sw: TStopwatch; HexStrings: TStringList; binaryString: string; begin HexStrings := TStringList.Create; try for Index := 0 to InputDataCount-1 do HexStrings.Add(RandomHexString(HexStringLength)); sw := TStopwatch.StartNew; for Iteration := 0 to IterationCount-1 do for Index := 0 to HexStrings.Count-1 do begin binaryString := HexToBin(HexStrings[Index]); binaryString := ''; // force a reallocation of the string every iteration of this loop end; Writeln('Pascal lookup: ', sw.ElapsedMilliseconds); sw := TStopwatch.StartNew; for Iteration := 0 to IterationCount-1 do for Index := 0 to HexStrings.Count-1 do begin binaryString := HexToBinAsm32(HexStrings[Index]); binaryString := ''; // force a reallocation of the string every iteration of this loop end; Writeln('asm32: ', sw.ElapsedMilliseconds); sw := TStopwatch.StartNew; for Iteration := 0 to IterationCount-1 do for Index := 0 to HexStrings.Count-1 do begin binaryString := HexToBinXmm(HexStrings[Index]); binaryString := ''; // force a reallocation of the string every iteration of this loop end; Writeln('xmm: ', sw.ElapsedMilliseconds); finally HexStrings.Free; end; end; begin try Randomize; Benchmark; except on E: Exception do Writeln(E.ClassName, ': ', E.Message); end; Readln; end. Compiled on XE7, 32 bit, release configuration OUTPUT: Pascal lookup: 3743 asm32: 4396 EAccessViolation: Access violation at address 004D77D3 in module 'Project14.exe'. Read of address FFFFFFFF The AV is HexToBinXmm. Perhaps I misunderstood something.
-
I made this benchmark program, that wraps your single digit asm into a function that handles string input, and included error checking. If you skip the error checking then your asm code is faster. But if you include error checking, not so. How would you go about integrating your single digit code into a string level function with error checking? Also, I'd love to have a high level explanation as to why my reasoning that a lookup table should not be beaten is wrong. Or is it perhaps that the implementation of the lookup table could be done better? {$APPTYPE CONSOLE} uses System.SysUtils, System.Classes, System.Diagnostics; //******************************************** // Constants to tune the benchmark performance const HexStringLength = 64; InputDataCount = 512; IterationCount = 20000; //***************************************************************** // David Heffernan's routine, with Move replace by Int64 assignment {$DEFINE ReplaceMoveWithInt64Assign} function HexToBin(const HexValue: string): string; const BinaryValues: array [0..15] of string = ( '0000', '0001', '0010', '0011', '0100', '0101', '0110', '0111', '1000', '1001', '1010', '1011', '1100', '1101', '1110', '1111' ); var HexDigit: Char; HexDigitValue: Integer; Ptr: PChar; begin SetLength(Result, Length(HexValue) * 4); Ptr := Pointer(Result); for HexDigit in HexValue do begin case HexDigit of '0'..'9': HexDigitValue := Ord(HexDigit) - Ord('0'); 'a'..'f': HexDigitValue := 10 + Ord(HexDigit) - Ord('a'); 'A'..'F': HexDigitValue := 10 + Ord(HexDigit) - Ord('A'); else raise EConvertError.CreateFmt('Invalid hex digit ''%s'' found in ''%s''', [HexDigit, HexValue]); end; {$IFDEF ReplaceMoveWithInt64Assign} PInt64(Ptr)^ := PInt64(BinaryValues[HexDigitValue])^; {$ELSE} Move(Pointer(BinaryValues[HexDigitValue])^, Ptr^, 4 * SizeOf(Char)); {$ENDIF} Inc(Ptr, 4); end; end; //********************* // Kas Ob's asm version procedure CharToBin_ASM32(HexChar: Char; HexBuffer: PChar); asm push edi mov edi,edx // Get the decimal value of one Hex Char (= half byte) movzx eax, HexChar mov ecx, 57 sub ecx, eax sar ecx, 31 and ecx, 39 neg ecx add eax, ecx add eax, - 48 // Produce 4 Chars presenting 4 bits of HexChar xor ecx,ecx mov dx,$1 test al,4 cmovne cx,dx shl ecx,16 test al,8 cmovne cx,dx add ecx,$00300030 mov [edi],ecx xor ecx,ecx test al,1 cmovne cx,dx shl ecx,16 test al,2 cmovne cx,dx add ecx,$00300030 mov [edi+4],ecx pop edi end; function HexToBinAsm(const HexValue: string): string; var HexDigit: Char; HexDigitValue: Integer; Ptr: PChar; begin SetLength(Result, Length(HexValue) * 4); Ptr := Pointer(Result); for HexDigit in HexValue do begin case HexDigit of '0'..'9','a'..'f','A'..'F': CharToBin_ASM32(HexDigit, Ptr); else raise EConvertError.CreateFmt('Invalid hex digit ''%s'' found in ''%s''', [HexDigit, HexValue]); end; Inc(Ptr, 4); end; end; //*************** // Benchmark code function RandomHexDigit: Char; var Ordinal: Integer; begin Ordinal := Random(16); case Ordinal of 0..9: Result := Chr(Ord('0') + Ordinal); 10..15: Result := Chr(Ord('a') + Ordinal - 10); else raise Exception.Create(''); end; end; function RandomHexString(Length: Integer): string; var Index: Integer; begin SetLength(Result, Length); for Index := 1 to Length do Result[Index] := RandomHexDigit; end; procedure Benchmark; var Index, Iteration: Integer; sw: TStopwatch; HexStrings: TStringList; binaryString: string; begin HexStrings := TStringList.Create; try for Index := 0 to InputDataCount-1 do HexStrings.Add(RandomHexString(HexStringLength)); sw := TStopwatch.StartNew; for Iteration := 0 to IterationCount-1 do for Index := 0 to HexStrings.Count-1 do begin binaryString := HexToBin(HexStrings[Index]); binaryString := ''; // force a reallocation of the string every iteration of this loop end; Writeln(sw.ElapsedMilliseconds); finally HexStrings.Free; end; end; begin try Randomize; Benchmark; except on E: Exception do Writeln(E.ClassName, ': ', E.Message); end; Readln; end. EDIT: It turns out that this benchmark is possibly useless at the moment, because HexToBinAsm doesn't work correctly (almost certainly my fault). I need to work out what I've done wrong. EDIT2: No, it's fine, I was mistaken, HexToBinAsm above works correctly.
-
My benchmarking suggests that point 1 has no impact on performance, but point 2 does. Actually the suggestion made by @Kas Ob. to replace the Move in my code with PInt64(Ptr)^ := PInt64(BinaryValues[HexDigitValue])^ is all you need to match the performance of your version. Which makes a lot of sense to me.
-
I think the way I phrased the question should help your intuition! 😉 It's always worth double checking, but a lookup table involves working the answer out before you compile. I would imagine it is hard for runtime code to ever beat that.
-
How do you think it will compare against a lookup table? How would you expect computing an answer at runtime compare to computing the answer before compile time?
-
No guarantee that an out of bounds array access leads to an exception. You have just been unlucky that you've seen one every time you ran your code. Once again, nobody should ever write code like that.
-
Holding the nibble binary text in a fixed length array is rather nice, I approve of that. Good stuff.
-
Fields of a class are default initialised upon instantiation. That means, for an integer, a value of 0. If you want to assign a different value, you need to do that yourself, in the constructor.
-
I'd probably write it something like this: function HexToBin(const HexValue: string): string; const BinaryValues: array [0..15] of string = ( '0000', '0001', '0010', '0011', '0100', '0101', '0110', '0111', '1000', '1001', '1010', '1011', '1100', '1101', '1110', '1111' ); var HexDigit: Char; HexDigitValue: Integer; Ptr: PChar; begin SetLength(Result, Length(HexValue) * 4); Ptr := Pointer(Result); for HexDigit in HexValue do begin case HexDigit of '0'..'9': HexDigitValue := Ord(HexDigit) - Ord('0'); 'a'..'f': HexDigitValue := 10 + Ord(HexDigit) - Ord('a'); 'A'..'F': HexDigitValue := 10 + Ord(HexDigit) - Ord('A'); else raise EConvertError.CreateFmt('Invalid hex digit ''%s'' found in ''%s''', [HexDigit, HexValue]); end; Move(Pointer(BinaryValues[HexDigitValue])^, Ptr^, 4 * SizeOf(Char)); Inc(Ptr, 4); end; end; Some notes: A case statement makes this quite readable in my view. You really don't want to be wasting time using Pos to search within a string. You can get the value directly with arithmetic. I prefer to perform just a single allocation, rather than use repeated allocations with concatenation. You might want to consider how to treat leading zeros. For instance how should you treat 0F, should that be 00001111 or 1111? I'd expect that both would be desirable in different situations, so an option in an extra argument to the function would be needed.
-
Ugh. You can't rely on getting an AV. Don't ever write code like this.
-
Define a simple map from the 16 hex digits to the 4 character binary strings. Iterate over each hex digit and concatenate.
-
So it doesn't say that the dpr file is missing. It says that the system unit is missing. This is possibly an issue with how you installed delphi. Or some erroneous settings in the existing project files.
-
Can 32bit dll with Form/Frame be used in 64 bit project?
David Heffernan replied to Mike Torrettinni's topic in VCL
Absolute insanity to attempt cross process window parent / child relationships. Not supported by MS amongst many many problems. Read what Raymond Chen has to say on the matter. It blows my mind that people keep on suggesting this. -
Can 32bit dll with Form/Frame be used in 64 bit project?
David Heffernan replied to Mike Torrettinni's topic in VCL
Cross process window parent relationships are something that in principle can be done, but in practise seldom work out. In reality the shortest route to your goal is almost certainly to replace the charting code. With an added benefit of also being the long term solution. -
Can 32bit dll with Form/Frame be used in 64 bit project?
David Heffernan replied to Mike Torrettinni's topic in VCL
"Can 32bit dll with Form/Frame be used in 64 bit project?" No. You can't mix different bitness modules in the same process. -
I've spoken to Marco enough times about this. Perhaps they'll have the sense to invite me anyway.
-
I can't sign up for the beta because I don't have a subscription. Does partaking in the beta have much impact?
-
I also would be ecstatic if this was delivered effectively.
-
Yeah in virtual mode you can't query the control, because it does not hold the data. You just query the data structure that does hold the data, a string list in your case.
-
Why are you trying to access the list views items when in virtual mode? That's directly against the concept of virtual mode.
-
try Foo := TFooBar.Create; ... finally Foo.Free; end; Consider the above. Suppose that TFooBar.Create raises an exception. In that case the finally block is executed, and `Foo.Free` is called on an uninitialised variable (Foo). That leads to undefined behaviour. So the correct pattern is Foo := TFooBar.Create; try ... finally Foo.Free; end; Here, if TFooBar.Create raises an exception, the try is never reached, and so the finally block never executes. Now another pattern was also mentioned Foo := nil; try Foo := TFooBar.Create; ... finally Foo.Free; end; This is also valid, because Foo is initialised before the try executes. And so in case of constructor exception we would call Free on a nil reference which is fine. However, this pattern is pointless and should be avoided in the scenario here where there is just a single object. It is useful sometimes if there are multiple objects and you want to avoid deep nesting. A better example of using this pattern is if the object is created conditionally: Foo := nil; try if someTest then begin Foo := TFooBar.Create; ... end; ... finally Foo.Free; end;
-
That would be nice. But in my experience, developing a program to work well with NUMA requires detailed knowledge from the programmer. I personally don't think there is any way round that.
-
You aren't going to get anywhere by just adding a new library, compiling, running, and hoping for magic. It's going to require in depth understanding if how to configure and use any library and how to adapt your own code.
-
Just remembered, doesn't FastMM5 have some features to support NUMA? Worth a look.