www.digitalmars.com         C & C++   DMDScript  

digitalmars.D.learn - Can this implementation of Damm algorithm be optimized?

reply Nestor <nestorperez2016 yopmail.com> writes:
Hi,

I was trying to port C code from the article in Wikiversity [1] 
to D, but I'm not sure this implementation is the most efficient 
way to do it in D, so suggestions to optimize it are welcome:

import std.stdio;

static immutable char[] QG10Matrix =
   "03175986427092154863420687135917509834266123045978" ~
   "36742095815869720134894536201794386172052581436790";

char checkDigit(string str) {
   char tmpdigit = '0';
   foreach(chr; str) tmpdigit = QG10Matrix[(chr - '0') + (tmpdigit 
- '0') * 10];
   return tmpdigit;
}

enum {
   EXIT_SUCCESS = 0,
   EXIT_FAILURE = 1,
}

int main(string[] args) {
   scope(failure) {
     writeln("Invalid arguments. You must pass a number.");
     return EXIT_FAILURE;
   }
   assert(args.length == 2);
   char digit = checkDigit(args[1]);
   if(digit == '0') writefln("%s is a valid number.", args[1]);
   else {
     writefln("%s is not a valid number (but it would be, 
appending digit %s).",
       args[1], digit);
   }

   return EXIT_SUCCESS;
}

[1] https://en.wikiversity.org/wiki/Damm_algorithm
Feb 09
next sibling parent Cym13 <cpicard openmailbox.org> writes:
On Thursday, 9 February 2017 at 17:36:11 UTC, Nestor wrote:
 Hi,

 I was trying to port C code from the article in Wikiversity [1] 
 to D, but I'm not sure this implementation is the most 
 efficient way to do it in D, so suggestions to optimize it are 
 welcome:

 import std.stdio;

 static immutable char[] QG10Matrix =
   "03175986427092154863420687135917509834266123045978" ~
   "36742095815869720134894536201794386172052581436790";

 char checkDigit(string str) {
   char tmpdigit = '0';
   foreach(chr; str) tmpdigit = QG10Matrix[(chr - '0') + 
 (tmpdigit - '0') * 10];
   return tmpdigit;
 }

 enum {
   EXIT_SUCCESS = 0,
   EXIT_FAILURE = 1,
 }

 int main(string[] args) {
   scope(failure) {
     writeln("Invalid arguments. You must pass a number.");
     return EXIT_FAILURE;
   }
   assert(args.length == 2);
   char digit = checkDigit(args[1]);
   if(digit == '0') writefln("%s is a valid number.", args[1]);
   else {
     writefln("%s is not a valid number (but it would be, 
 appending digit %s).",
       args[1], digit);
   }

   return EXIT_SUCCESS;
 }

 [1] https://en.wikiversity.org/wiki/Damm_algorithm
I can't see how to make it more efficient than it is (aside from finding a better algorithm which isn't a language concern). You are using C style and will get the same machine code as if you'd written it with C. The only difference would be boundchecking that you can disable by using the -boundscheck=off compiler switch. By the way note that you can use the -profile switch to see where the bottlenecks are, in your case writting the result to stdout is *by far* what takes the most time (and I'm quite certain the bottleneck is the same in the C version for it's a fact that I/O is slow).
Feb 09
prev sibling parent reply Era Scarecrow <rtcvb32 yahoo.com> writes:
On Thursday, 9 February 2017 at 17:36:11 UTC, Nestor wrote:
 I was trying to port C code from the article in Wikiversity [1] 
 to D, but I'm not sure this implementation is the most 
 efficient way to do it in D, so suggestions to optimize it are 
 welcome:

 import std.stdio;

 static immutable char[] QG10Matrix =
   "03175986427092154863420687135917509834266123045978" ~
   "36742095815869720134894536201794386172052581436790";

 char checkDigit(string str) {
   char tmpdigit = '0';
   foreach(chr; str) tmpdigit = QG10Matrix[(chr - '0') + 
 (tmpdigit - '0') * 10];
   return tmpdigit;
 }
Well one thing is you can probably reduce them from chars to just bytes, instead of having to subtract you can instead add at the end. Although unless you're working with a VERY large input you won't see a difference. Actually since you're also multiplying by 10, you can incorporate that in the table too... (although a mixin might be better for the conversion than by hand) static immutable char[] QG10Matrix = [ 00,30,10,70,50,90,80,60,40,20, 70,00,90,20,10,50,40,80,60,30, 40,20,00,60,80,70,10,30,50,90, 10,70,50,00,90,80,30,40,20,60, 60,10,20,30,00,40,50,90,70,80, 30,60,70,40,20,00,90,50,80,10, 50,80,60,90,70,20,00,10,30,40, 80,90,40,50,30,60,20,00,10,70, 90,40,30,80,60,10,70,20,00,50, 20,50,80,10,40,30,60,70,90,00]; char checkDigit(string str) { char tmpdigit = 0; foreach(chr; str) tmpdigit = QG10Matrix[(chr - '0') + tmpdigit]; return (tmpdigit/10) + '0'; }
Feb 09
next sibling parent reply Nestor <nestorperez2016 yopmail.com> writes:
On Thursday, 9 February 2017 at 18:34:30 UTC, Era Scarecrow wrote:
 On Thursday, 9 February 2017 at 17:36:11 UTC, Nestor wrote:
 I was trying to port C code from the article in Wikiversity 
 [1] to D, but I'm not sure this implementation is the most 
 efficient way to do it in D, so suggestions to optimize it are 
 welcome:

 import std.stdio;

 static immutable char[] QG10Matrix =
   "03175986427092154863420687135917509834266123045978" ~
   "36742095815869720134894536201794386172052581436790";

 char checkDigit(string str) {
   char tmpdigit = '0';
   foreach(chr; str) tmpdigit = QG10Matrix[(chr - '0') + 
 (tmpdigit - '0') * 10];
   return tmpdigit;
 }
Well one thing is you can probably reduce them from chars to just bytes, instead of having to subtract you can instead add at the end. Although unless you're working with a VERY large input you won't see a difference. Actually since you're also multiplying by 10, you can incorporate that in the table too... (although a mixin might be better for the conversion than by hand) static immutable char[] QG10Matrix = [ 00,30,10,70,50,90,80,60,40,20, 70,00,90,20,10,50,40,80,60,30, 40,20,00,60,80,70,10,30,50,90, 10,70,50,00,90,80,30,40,20,60, 60,10,20,30,00,40,50,90,70,80, 30,60,70,40,20,00,90,50,80,10, 50,80,60,90,70,20,00,10,30,40, 80,90,40,50,30,60,20,00,10,70, 90,40,30,80,60,10,70,20,00,50, 20,50,80,10,40,30,60,70,90,00]; char checkDigit(string str) { char tmpdigit = 0; foreach(chr; str) tmpdigit = QG10Matrix[(chr - '0') + tmpdigit]; return (tmpdigit/10) + '0'; }
OK I changed the approach using a multidimensional array for the matrix so I could ditch arithmetic operations altogether, but curiously after measuring a few thousand runs of both implementations through avgtime, I see no noticeable difference. Why? import std.stdio; static immutable ubyte[][] QG10Matrix = [ [0,3,1,7,5,9,8,6,4,2],[7,0,9,2,1,5,4,8,6,3], [4,2,0,6,8,7,1,3,5,9],[1,7,5,0,9,8,3,4,2,6], [6,1,2,3,0,4,5,9,7,8],[3,6,7,4,2,0,9,5,8,1], [5,8,6,9,7,2,0,1,3,4],[8,9,4,5,3,6,2,0,1,7], [9,4,3,8,6,1,7,2,0,5],[2,5,8,1,4,3,6,7,9,0], ]; static int charToInt(char chr) { scope(failure) return -1; return cast(int)(chr - '0'); } ubyte checkDigit(string str) { ubyte tmpdigit; foreach(chr; str) tmpdigit = QG10Matrix[tmpdigit][charToInt(chr)]; return tmpdigit; } enum { EXIT_SUCCESS = 0, EXIT_FAILURE = 1, } int main(string[] args) { scope(failure) { writeln("Invalid arguments. You must pass a number."); return EXIT_FAILURE; } assert(args.length == 2); ubyte digit = checkDigit(args[1]); if(digit == 0) writefln("%s is a valid number.", args[1]); else { writefln("%s is not a valid number (but it would be, appending digit %s).", args[1], digit); } return EXIT_SUCCESS; }
Feb 09
next sibling parent reply Daniel Kozak via Digitalmars-d-learn <digitalmars-d-learn puremagic.com> writes:
Dne 9.2.2017 v 20:39 Nestor via Digitalmars-d-learn napsal(a):

 On Thursday, 9 February 2017 at 18:34:30 UTC, Era Scarecrow wrote:
 On Thursday, 9 February 2017 at 17:36:11 UTC, Nestor wrote:
 I was trying to port C code from the article in Wikiversity [1] to 
 D, but I'm not sure this implementation is the most efficient way to 
 do it in D, so suggestions to optimize it are welcome:

 import std.stdio;

 static immutable char[] QG10Matrix =
   "03175986427092154863420687135917509834266123045978" ~
   "36742095815869720134894536201794386172052581436790";

 char checkDigit(string str) {
   char tmpdigit = '0';
   foreach(chr; str) tmpdigit = QG10Matrix[(chr - '0') + (tmpdigit - 
 '0') * 10];
   return tmpdigit;
 }
Well one thing is you can probably reduce them from chars to just bytes, instead of having to subtract you can instead add at the end. Although unless you're working with a VERY large input you won't see a difference. Actually since you're also multiplying by 10, you can incorporate that in the table too... (although a mixin might be better for the conversion than by hand) static immutable char[] QG10Matrix = [ 00,30,10,70,50,90,80,60,40,20, 70,00,90,20,10,50,40,80,60,30, 40,20,00,60,80,70,10,30,50,90, 10,70,50,00,90,80,30,40,20,60, 60,10,20,30,00,40,50,90,70,80, 30,60,70,40,20,00,90,50,80,10, 50,80,60,90,70,20,00,10,30,40, 80,90,40,50,30,60,20,00,10,70, 90,40,30,80,60,10,70,20,00,50, 20,50,80,10,40,30,60,70,90,00]; char checkDigit(string str) { char tmpdigit = 0; foreach(chr; str) tmpdigit = QG10Matrix[(chr - '0') + tmpdigit]; return (tmpdigit/10) + '0'; }
OK I changed the approach using a multidimensional array for the matrix so I could ditch arithmetic operations altogether, but curiously after measuring a few thousand runs of both implementations through avgtime, I see no noticeable difference. Why? import std.stdio; static immutable ubyte[][] QG10Matrix = [ [0,3,1,7,5,9,8,6,4,2],[7,0,9,2,1,5,4,8,6,3], [4,2,0,6,8,7,1,3,5,9],[1,7,5,0,9,8,3,4,2,6], [6,1,2,3,0,4,5,9,7,8],[3,6,7,4,2,0,9,5,8,1], [5,8,6,9,7,2,0,1,3,4],[8,9,4,5,3,6,2,0,1,7], [9,4,3,8,6,1,7,2,0,5],[2,5,8,1,4,3,6,7,9,0], ]; static int charToInt(char chr) { scope(failure) return -1; return cast(int)(chr - '0'); } ubyte checkDigit(string str) { ubyte tmpdigit; foreach(chr; str) tmpdigit = QG10Matrix[tmpdigit][charToInt(chr)]; return tmpdigit; } enum { EXIT_SUCCESS = 0, EXIT_FAILURE = 1, } int main(string[] args) { scope(failure) { writeln("Invalid arguments. You must pass a number."); return EXIT_FAILURE; } assert(args.length == 2); ubyte digit = checkDigit(args[1]); if(digit == 0) writefln("%s is a valid number.", args[1]); else { writefln("%s is not a valid number (but it would be, appending digit %s).", args[1], digit); } return EXIT_SUCCESS; }
Maybe you can try use static array instead of dynamic static immutable ubyte[10][10] QG10Matrix = ...
Feb 09
parent reply Nestor <nestorperez2016 yopmail.com> writes:
On Thursday, 9 February 2017 at 20:46:06 UTC, Daniel Kozak wrote:
 Maybe you can try use static array instead of dynamic
 static immutable ubyte[10][10] QG10Matrix = ...
I shaved it to this to discard unneccessary time-consuming functions: static immutable ubyte[10][10] QG10Matrix = [ [0,3,1,7,5,9,8,6,4,2],[7,0,9,2,1,5,4,8,6,3], [4,2,0,6,8,7,1,3,5,9],[1,7,5,0,9,8,3,4,2,6], [6,1,2,3,0,4,5,9,7,8],[3,6,7,4,2,0,9,5,8,1], [5,8,6,9,7,2,0,1,3,4],[8,9,4,5,3,6,2,0,1,7], [9,4,3,8,6,1,7,2,0,5],[2,5,8,1,4,3,6,7,9,0], ]; static immutable string number = "0123456789012345678901234567890123456789012345678901234567890123456789"; static int charToInt(char chr) { return ((chr >= '0') || (chr <= '9')) ? cast(int)(chr - '0') : -1; } ubyte checkDigit(string str) { ubyte tmpdigit; foreach(chr; str) tmpdigit = QG10Matrix[tmpdigit][charToInt(chr)]; return tmpdigit; } void main() { auto digit = checkDigit(number); } I even tried making checkDigit static, but surprisingly this increased average execution time by 1ms. Anyway, the previopus version (modified to benefit from a little optimization too) is almost as performant, even though it includes multiplication and sum: static immutable char[] QG10Matrix = "03175986427092154863420687135917509834266123045978" ~ "36742095815869720134894536201794386172052581436790"; static immutable string number = "0123456789012345678901234567890123456789012345678901234567890123456789"; static int charToInt(char chr) { return ((chr >= '0') || (chr <= '9')) ? cast(int)(chr - '0') : -1; } char checkDigit(string str) { char tmpdigit = '0'; foreach(chr; str) tmpdigit = QG10Matrix[charToInt(chr) + (charToInt(tmpdigit) * 10)]; return tmpdigit; } void main() { auto digit = checkDigit(number); } I compiled both with -inline -noboundscheck -release and the multidimensional array version does perform 1ms faster for a couple hundred runs, but I expected the difference to be much more noticeable. Any idea of what might be happening here?
Feb 09
parent reply Daniel Kozak via Digitalmars-d-learn <digitalmars-d-learn puremagic.com> writes:
Dne 9.2.2017 v 22:29 Nestor via Digitalmars-d-learn napsal(a):

 On Thursday, 9 February 2017 at 20:46:06 UTC, Daniel Kozak wrote:
 Maybe you can try use static array instead of dynamic
 static immutable ubyte[10][10] QG10Matrix = ...
I shaved it to this to discard unneccessary time-consuming functions: static immutable ubyte[10][10] QG10Matrix = [ [0,3,1,7,5,9,8,6,4,2],[7,0,9,2,1,5,4,8,6,3], [4,2,0,6,8,7,1,3,5,9],[1,7,5,0,9,8,3,4,2,6], [6,1,2,3,0,4,5,9,7,8],[3,6,7,4,2,0,9,5,8,1], [5,8,6,9,7,2,0,1,3,4],[8,9,4,5,3,6,2,0,1,7], [9,4,3,8,6,1,7,2,0,5],[2,5,8,1,4,3,6,7,9,0], ]; static immutable string number = "0123456789012345678901234567890123456789012345678901234567890123456789"; static int charToInt(char chr) { return ((chr >= '0') || (chr <= '9')) ? cast(int)(chr - '0') : -1; } ubyte checkDigit(string str) { ubyte tmpdigit; foreach(chr; str) tmpdigit = QG10Matrix[tmpdigit][charToInt(chr)]; return tmpdigit; } void main() { auto digit = checkDigit(number); } I even tried making checkDigit static, but surprisingly this increased average execution time by 1ms. Anyway, the previopus version (modified to benefit from a little optimization too) is almost as performant, even though it includes multiplication and sum: static immutable char[] QG10Matrix = "03175986427092154863420687135917509834266123045978" ~ "36742095815869720134894536201794386172052581436790"; static immutable string number = "0123456789012345678901234567890123456789012345678901234567890123456789"; static int charToInt(char chr) { return ((chr >= '0') || (chr <= '9')) ? cast(int)(chr - '0') : -1; } char checkDigit(string str) { char tmpdigit = '0'; foreach(chr; str) tmpdigit = QG10Matrix[charToInt(chr) + (charToInt(tmpdigit) * 10)]; return tmpdigit; } void main() { auto digit = checkDigit(number); } I compiled both with -inline -noboundscheck -release and the multidimensional array version does perform 1ms faster for a couple hundred runs, but I expected the difference to be much more noticeable. Any idea of what might be happening here?
Did you try it with different backends? llvm (ldc), gcc(gdc)?
Feb 09
parent reply Nestor <nestorperez2016 yopmail.com> writes:
On Thursday, 9 February 2017 at 21:43:08 UTC, Daniel Kozak wrote:
 Any idea of what might be happening here?
Did you try it with different backends? llvm (ldc), gcc(gdc)?
Not really, just standard dmd. I tried running each algoritm a few times through avgtime using different digit lengths (upto 10,000, my PC won't handle much more) and different amount of repetitions, and the results aren't consistent, some times one algorithm is marginally faster, sometimes the other. Apparently the compiler is capable of optimizing the unidimensional array version. Thank you all nevertheless for the suggestions.
Feb 09
parent reply =?UTF-8?Q?Ali_=c3=87ehreli?= <acehreli yahoo.com> writes:
On 02/09/2017 02:04 PM, Nestor wrote:

 I tried running each algoritm a few times through avgtime using
 different digit lengths
avgtime profiles the whole process, right? It measures everything that is involved in that little program. At least OS starting the program, D runtime initializing, program interacting with the console, etc. Since you're comparing algorithms, you need to take everything else out of the equation. A better approach is to use std.datetime.benchmark, which would repeat just the algorithm that you're interested in. Ali
Feb 09
parent Daniel Kozak via Digitalmars-d-learn <digitalmars-d-learn puremagic.com> writes:
Dne 9.2.2017 v 23:08 Ali Çehreli via Digitalmars-d-learn napsal(a):

 On 02/09/2017 02:04 PM, Nestor wrote:

 I tried running each algoritm a few times through avgtime using
 different digit lengths
avgtime profiles the whole process, right? It measures everything that is involved in that little program. At least OS starting the program, D runtime initializing, program interacting with the console, etc. Since you're comparing algorithms, you need to take everything else out of the equation. A better approach is to use std.datetime.benchmark, which would repeat just the algorithm that you're interested in. Ali
Yes this is important, and for example when you used shared libphobos it makes really big difference
Feb 09
prev sibling next sibling parent Cym13 <cpicard openmailbox.org> writes:
On Thursday, 9 February 2017 at 19:39:49 UTC, Nestor wrote:
 On Thursday, 9 February 2017 at 18:34:30 UTC, Era Scarecrow 
 wrote:
 On Thursday, 9 February 2017 at 17:36:11 UTC, Nestor wrote:
 I was trying to port C code from the article in Wikiversity 
 [1] to D, but I'm not sure this implementation is the most 
 efficient way to do it in D, so suggestions to optimize it 
 are welcome:

 import std.stdio;

 static immutable char[] QG10Matrix =
   "03175986427092154863420687135917509834266123045978" ~
   "36742095815869720134894536201794386172052581436790";

 char checkDigit(string str) {
   char tmpdigit = '0';
   foreach(chr; str) tmpdigit = QG10Matrix[(chr - '0') + 
 (tmpdigit - '0') * 10];
   return tmpdigit;
 }
Well one thing is you can probably reduce them from chars to just bytes, instead of having to subtract you can instead add at the end. Although unless you're working with a VERY large input you won't see a difference. Actually since you're also multiplying by 10, you can incorporate that in the table too... (although a mixin might be better for the conversion than by hand) static immutable char[] QG10Matrix = [ 00,30,10,70,50,90,80,60,40,20, 70,00,90,20,10,50,40,80,60,30, 40,20,00,60,80,70,10,30,50,90, 10,70,50,00,90,80,30,40,20,60, 60,10,20,30,00,40,50,90,70,80, 30,60,70,40,20,00,90,50,80,10, 50,80,60,90,70,20,00,10,30,40, 80,90,40,50,30,60,20,00,10,70, 90,40,30,80,60,10,70,20,00,50, 20,50,80,10,40,30,60,70,90,00]; char checkDigit(string str) { char tmpdigit = 0; foreach(chr; str) tmpdigit = QG10Matrix[(chr - '0') + tmpdigit]; return (tmpdigit/10) + '0'; }
OK I changed the approach using a multidimensional array for the matrix so I could ditch arithmetic operations altogether, but curiously after measuring a few thousand runs of both implementations through avgtime, I see no noticeable difference. Why? import std.stdio; static immutable ubyte[][] QG10Matrix = [ [0,3,1,7,5,9,8,6,4,2],[7,0,9,2,1,5,4,8,6,3], [4,2,0,6,8,7,1,3,5,9],[1,7,5,0,9,8,3,4,2,6], [6,1,2,3,0,4,5,9,7,8],[3,6,7,4,2,0,9,5,8,1], [5,8,6,9,7,2,0,1,3,4],[8,9,4,5,3,6,2,0,1,7], [9,4,3,8,6,1,7,2,0,5],[2,5,8,1,4,3,6,7,9,0], ]; static int charToInt(char chr) { scope(failure) return -1; return cast(int)(chr - '0'); } ubyte checkDigit(string str) { ubyte tmpdigit; foreach(chr; str) tmpdigit = QG10Matrix[tmpdigit][charToInt(chr)]; return tmpdigit; } enum { EXIT_SUCCESS = 0, EXIT_FAILURE = 1, } int main(string[] args) { scope(failure) { writeln("Invalid arguments. You must pass a number."); return EXIT_FAILURE; } assert(args.length == 2); ubyte digit = checkDigit(args[1]); if(digit == 0) writefln("%s is a valid number.", args[1]); else { writefln("%s is not a valid number (but it would be, appending digit %s).", args[1], digit); } return EXIT_SUCCESS; }
The question is, why do you expect it to be noticably faster? On modern hardware it the optimizations are such that so little a change in code is very hard to link to a difference in running time. If you really want to show one the following code does the benchmark the right way (ie: using a very long input, tens of thousands of runs, and avoiding I/O and load time of the program to compare the bare function implementations): import std.conv; import std.stdio; import std.range; import std.array; import std.algorithm; string testcase; static immutable char[] QG10MatrixOne = "03175986427092154863420687135917509834266123045978" ~ "36742095815869720134894536201794386172052581436790"; char checkDigitOne(string str) { char tmpdigit = 0; foreach(chr; str) tmpdigit = QG10MatrixOne[(chr - '0') + (tmpdigit - '0') * 10]; return tmpdigit; } void testCheckDigitOne() { checkDigitTwo(testcase); } static immutable ubyte[][] QG10MatrixTwo = [ [0,3,1,7,5,9,8,6,4,2],[7,0,9,2,1,5,4,8,6,3], [4,2,0,6,8,7,1,3,5,9],[1,7,5,0,9,8,3,4,2,6], [6,1,2,3,0,4,5,9,7,8],[3,6,7,4,2,0,9,5,8,1], [5,8,6,9,7,2,0,1,3,4],[8,9,4,5,3,6,2,0,1,7], [9,4,3,8,6,1,7,2,0,5],[2,5,8,1,4,3,6,7,9,0], ]; static int charToInt(char chr) { scope(failure) return -1; return cast(int)(chr - '0'); } ubyte checkDigitTwo(string str) { ubyte tmpdigit; foreach(chr; str) { tmpdigit = QG10MatrixTwo[tmpdigit][charToInt(chr)]; } return tmpdigit; } void testCheckDigitTwo() { checkDigitTwo(testcase); } void main(string[] args) { testcase = iota(10).cycle.take(100000).map!(to!string).array.join; import std.datetime: benchmark; benchmark!(testCheckDigitOne, testCheckDigitTwo)(10000).each!writeln; } Yet on my machine I have the following times (note that the time itself depends on my hardware, what's important is the difference): TickDuration(15785255852) TickDuration(15784826803) So it seems that the first version is slower than the second one, but by so little that it's hard to link to the actual implementation. If anything it shows the futility of such low-level tricks for meaningless optimization. And by the way note that the benchmark avoid measuring IO because we were interested in the functions. But if we were measuring it it would represent 4 fifth of the running time (on my machine, with numbers as long as the one used in the benchmark). This means even a 20% improvement in checkDigit would actually only represent a 4% improvement of the program.
Feb 09
prev sibling parent reply Era Scarecrow <rtcvb32 yahoo.com> writes:
On Thursday, 9 February 2017 at 19:39:49 UTC, Nestor wrote:
 OK I changed the approach using a multidimensional array for 
 the matrix so I could ditch arithmetic operations altogether, 
 but curiously after measuring a few thousand runs of both 
 implementations through avgtime, I see no noticeable 
 difference. Why?
Truthfully, because you'll need tens of millions or hundreds of millions in length to determine if it makes a difference and how much. Addition, subtraction and simple memory lookups take very little time, and since the entire array (100 bytes) fits in the cache, it is going to perform very very very well regardless if you can optimize it further. If you tested this on a much slower system, say an 8bit 6502 the differences would be far more pronounced, but not that much different. Since the algorithm is more or less O(n) optimizing it won't make many differences. It's possible you could get a speedup by making them ints instead of chars, since then it might not have a penalty for the 'address not divisible by 4' that applies (which is more for ARM architectures and less for x86). Other optimizations could be to make it multiple levels, taking the basic 100 elements and expanding them 2-3 levels deep in a lookup and having it do it in more or less a single operation. (100 bytes for 1 level, 10,000 for 2 levels, 1,000,000 for 3 levels, 100,000,000 for 4 levels, etc), but the steps of converting it to the array lookup won't give you that much gain, although fewer memory lookups but none of them will be cached, so any advantage from that is probably lost. Although if you bump up the size to 16x10 instead of 10x10, you could use a shift instead of *10 which will make that slightly faster (there will be unused empty padded spots) In theory if you avoid the memory lookup at all, you could gain some amount of speed, depending on how it searches a manual table, although using a switch-case and a mixin to do all the details it feels like it wouldn't give you any gain... Division operations are the slowest operations you can do, but otherwise most instructions run really fast. Unless you're trying to get it smaller (fewer bytes for the call) or shaving for speed by instruction cycle counting (like on the 6502) i doubt you'll get much benefit.
Feb 09
parent reply Nestor <nestorperez2016 yopmail.com> writes:
On Thursday, 9 February 2017 at 23:49:19 UTC, Era Scarecrow wrote:
  Other optimizations could be to make it multiple levels, 
 taking the basic 100 elements and expanding them 2-3 levels 
 deep in a lookup and having it do it in more or less a single 
 operation. (100 bytes for 1 level, 10,000 for 2 levels, 
 1,000,000 for 3 levels, 100,000,000 for 4 levels, etc), but the 
 steps of converting it to the array lookup won't give you that 
 much gain, although fewer memory lookups but none of them will 
 be cached, so any advantage from that is probably lost. 
 Although if you bump up the size to 16x10 instead of 10x10, you 
 could use a shift instead of *10 which will make that slightly 
 faster (there will be unused empty padded spots)

  In theory if you avoid the memory lookup at all, you could 
 gain some amount of speed, depending on how it searches a 
 manual table, although using a switch-case and a mixin to do 
 all the details it feels like it wouldn't give you any gain...
Thank you for the detailed reply. I wasn't able to follow you regarding the multilevel stuff though :(
Feb 10
parent reply Era Scarecrow <rtcvb32 yahoo.com> writes:
On Friday, 10 February 2017 at 11:27:02 UTC, Nestor wrote:
 Thank you for the detailed reply. I wasn't able to follow you 
 regarding the multilevel stuff though :(
The idea behind it is like this (which you can scale up): static immutable int[] QG10Matrix2 = buildMatrix2(); int[] buildMatrix2() { string digits = "0123456789"; int[] l = new int[16*16*10]; char[3] s; foreach(a; digits) foreach(b; digits) foreach(c; digits) { s[] = [a,b,c]; l[(a-'0')<< 8|(b-'0')<<4|(c-'0')]=checkDigit(cast(string) s) - '0'; } return l; } Using that it SHOULD allow you to get the result of 2 inputs simply by using 2 characters (plus the old result) char checkDigit2(string str) { int tmpdigit = 0; for(;str.length >= 2;str=str[2 .. $]) { tmpdigit = QG10Matrix2[tmpdigit<<8|(str[0]-'0')<< 4|(str[1]-'0')]; } // handle remainder single character and return value While it should be easy, I'm having issues trying to get the proper results via unittests and I'm not sure why. Probably something incredibly simple on my part.
Feb 11
parent reply Nestor <nestorperez2016 yopmail.com> writes:
On Saturday, 11 February 2017 at 11:45:02 UTC, Era Scarecrow 
wrote:
 On Friday, 10 February 2017 at 11:27:02 UTC, Nestor wrote:
 Thank you for the detailed reply. I wasn't able to follow you 
 regarding the multilevel stuff though :(
The idea behind it is like this (which you can scale up): static immutable int[] QG10Matrix2 = buildMatrix2(); int[] buildMatrix2() { string digits = "0123456789"; int[] l = new int[16*16*10]; char[3] s; foreach(a; digits) foreach(b; digits) foreach(c; digits) { s[] = [a,b,c]; l[(a-'0')<< 8|(b-'0')<<4|(c-'0')]=checkDigit(cast(string) s) - '0'; } return l; } Using that it SHOULD allow you to get the result of 2 inputs simply by using 2 characters (plus the old result) char checkDigit2(string str) { int tmpdigit = 0; for(;str.length >= 2;str=str[2 .. $]) { tmpdigit = QG10Matrix2[tmpdigit<<8|(str[0]-'0')<< 4|(str[1]-'0')]; } // handle remainder single character and return value While it should be easy, I'm having issues trying to get the proper results via unittests and I'm not sure why. Probably something incredibly simple on my part.
Notice this is no ordinary matrix, but an Anti-Simmetric QuasiGroup of order 10, and tmpdigit (called interim in the algorithm) is used in each round (although the function isn't recursive) together with each digit to calculate final check digit.
Feb 11
parent reply Era Scarecrow <rtcvb32 yahoo.com> writes:
On Saturday, 11 February 2017 at 20:19:51 UTC, Nestor wrote:
 Notice this is no ordinary matrix, but an Anti-Simmetric 
 QuasiGroup of order 10, and tmpdigit (called interim in the 
 algorithm) is used in each round (although the function isn't 
 recursive) together with each digit to calculate final check 
 digit.
Yes i know, which is why i had 3 to calculate 2 inputs because the third is the temp/previous calculation. If however you were calculating a fixed number of digits a single table could be made and do a single lookup, assuming it wasn't too large to make it uncumbersome or impractical.
Feb 11
parent reply Era Scarecrow <rtcvb32 yahoo.com> writes:
On Saturday, 11 February 2017 at 21:02:40 UTC, Era Scarecrow 
wrote:
  Yes i know, which is why i had 3 to calculate 2 inputs because 
 the third is the temp/previous calculation.
Alright I've found the bug and fixed it, and it passes with flying colors (brute force tests up to 6 digits); However it doesn't use the original function to build the table. So I'm satisfied it will handle any length now. But it seriously is a lot of overhead for such a simple function. int[] buildMatrix2() { string digits = "0123456789"; int[] l = new int[16*16*10]; l[] = -1; //printing the array it's obvious to see what is padding foreach(a; digits) foreach(b; digits) foreach(c; digits) { int t = (a-'0')*10, t2 = (QG10Matrix[(b - '0') + t]-'0') * 10, off = (a - '0') << 8 | (b - '0') << 4 | (c - '0'); l[off] = (QG10Matrix[(c - '0') + t2]-'0')<<8; } return l; } char checkDigit2(string str) { int tmpdigit = 0; for(;str.length >= 2;str = str[2 .. $]) tmpdigit = QG10Matrix2[tmpdigit|(str[0]-'0')<<4|(str[1]-'0')]; tmpdigit>>=8; if (str.length==1) return QG10Matrix[(str[0]-'0')+tmpdigit*10]; return (tmpdigit+'0') & 0xff; }
Feb 11
next sibling parent reply Era Scarecrow <rtcvb32 yahoo.com> writes:
On Saturday, 11 February 2017 at 21:41:11 UTC, Era Scarecrow 
wrote:
  But it seriously is a lot of overhead for such a simple 
 function.
Just ran the unittests under the dmd profiler, says the algorithm is 11% faster now. So yeah slightly more optimized. Another level and we could probably get 25%, but the built matrix will blow up far larger than the 10k it is now. Num Tree Func Per Calls Time Time Call 12000000 1281989 1281989 0 char damm.checkDigit(immutable(char)[]) 12000000 1146308 1146308 0 char damm.checkDigit2(immutable(char)[])
Feb 11
parent reply Era Scarecrow <rtcvb32 yahoo.com> writes:
On Saturday, 11 February 2017 at 21:56:54 UTC, Era Scarecrow 
wrote:
  Just ran the unittests under the dmd profiler, says the 
 algorithm is 11% faster now. So yeah slightly more optimized.
Ran some more tests. Without optimization but with with 4 levels (a 2.5Mb table), it gains to a whopping 27%! However with optimizations turned on it dwindled to a mere 15% boost And optimization + no bounds checking, 2 & 4 levels both give a 9% boost total. Testing purely on 8byte inputs (Brute forced all combinations) receives the same 9% boost with negligible difference. Safe to say going higher levels isn't going to give you sufficient improvement; Also exe file is 3Mb big (but compresses to 150k).
Feb 11
parent reply Nestor <nestorperez2016 yopmail.com> writes:
On Sunday, 12 February 2017 at 05:54:34 UTC, Era Scarecrow wrote:
 On Saturday, 11 February 2017 at 21:56:54 UTC, Era Scarecrow 
 wrote:
  Just ran the unittests under the dmd profiler, says the 
 algorithm is 11% faster now. So yeah slightly more optimized.
Ran some more tests. Without optimization but with with 4 levels (a 2.5Mb table), it gains to a whopping 27%! However with optimizations turned on it dwindled to a mere 15% boost And optimization + no bounds checking, 2 & 4 levels both give a 9% boost total. Testing purely on 8byte inputs (Brute forced all combinations) receives the same 9% boost with negligible difference. Safe to say going higher levels isn't going to give you sufficient improvement; Also exe file is 3Mb big (but compresses to 150k).
Wow! Thanks for the interest and effort.
Feb 12
parent Era Scarecrow <rtcvb32 yahoo.com> writes:
On Monday, 13 February 2017 at 00:56:37 UTC, Nestor wrote:
 On Sunday, 12 February 2017 at 05:54:34 UTC, Era Scarecrow 
 wrote:
 Ran some more tests.
Wow! Thanks for the interest and effort.
Certainly. But the bulk of the answer comes down that the 2 levels that I've already provided are the fastest you're probably going to get. Certainly we can test using shorts or bytes instead, but it's likely the results will only go down. To note my tests are strictly on my x86 system and it would be better to also test this on other systems like PPC, Linux, ARM, and other architectures to see how they perform, and possibly tweak them as appropriate. Still we did find out there is some optimization that can be done and successfully for the Damm algorithm, it just isn't going to be a lot. Hmmm... A thought does come to mind. Parallelizing the code; However that would require probably 11 instances to get a 2x speedup (calculating the second half with all 10 possibilities for the carry over, and also calculating the first half, then choosing which of the 10 based on the first half's output), which only really works if you have a ton of cores, and the input is REALLY REALLY large, like a meg or something. While the usage of the Damm code is more useful for adding a digit to the end of a code like UPC or Barcodes as error detection, and expecting larger than 32 for real applications is unlikely. But at this point I'm rambling.
Feb 12
prev sibling parent reply Nestor <nestorperez2016 yopmail.com> writes:
On Saturday, 11 February 2017 at 21:41:11 UTC, Era Scarecrow 
wrote:
 On Saturday, 11 February 2017 at 21:02:40 UTC, Era Scarecrow 
 wrote:
  Yes i know, which is why i had 3 to calculate 2 inputs 
 because the third is the temp/previous calculation.
Alright I've found the bug and fixed it, and it passes with flying colors (brute force tests up to 6 digits); However it doesn't use the original function to build the table. So I'm satisfied it will handle any length now. But it seriously is a lot of overhead for such a simple function. int[] buildMatrix2() { string digits = "0123456789"; int[] l = new int[16*16*10]; l[] = -1; //printing the array it's obvious to see what is padding foreach(a; digits) foreach(b; digits) foreach(c; digits) { int t = (a-'0')*10, t2 = (QG10Matrix[(b - '0') + t]-'0') * 10, off = (a - '0') << 8 | (b - '0') << 4 | (c - '0'); l[off] = (QG10Matrix[(c - '0') + t2]-'0')<<8; } return l; } char checkDigit2(string str) { int tmpdigit = 0; for(;str.length >= 2;str = str[2 .. $]) tmpdigit = QG10Matrix2[tmpdigit|(str[0]-'0')<<4|(str[1]-'0')]; tmpdigit>>=8; if (str.length==1) return QG10Matrix[(str[0]-'0')+tmpdigit*10]; return (tmpdigit+'0') & 0xff; }
I fail to see where you are declaring QG10Matrix2, because apparently it's an array of chars, but buildMatrix2 returns an array of int (2560 elements??) with lots of -1 values.
Feb 11
parent Era Scarecrow <rtcvb32 yahoo.com> writes:
On Sunday, 12 February 2017 at 00:43:55 UTC, Nestor wrote:
 I fail to see where you are declaring QG10Matrix2, because 
 apparently it's an array of chars, but buildMatrix2 returns an 
 array of int (2560 elements??) with lots of -1 values.
I declared it here: http://forum.dlang.org/post/fiamjuhiddbzwvaplxkr forum.dlang.org and it's not chars, it's ints. Part of it is to avoid the mem access penalty for non divisible by 4 addresses, and another is that the array returns not chars, but numbers from 0-2560, which is the answer *256 (<<8), which offers hopefully some slight speed gain on longer inputs. Also the size of the array is guesstimated, and the -1's just signify the padding (which can be any value, but -1 makes it obvious). Since it's a 10x10 array it's based on, but using 4bits per section, there's 6 elements lost, and 6 whole rows lost. It's a necessary loss to gain speed; Thankfully it's only using 10k (2560 members) and not 700k as was my original guess when i was calculating it wrong earlier. Doing it wrong earlier, the compiler kept crashing... :P running out of memory.
Feb 11
prev sibling parent Nestor <nestorperez2016 yopmail.com> writes:
On Thursday, 9 February 2017 at 18:34:30 UTC, Era Scarecrow wrote:
 ...
 Actually since you're also multiplying by 10, you can 
 incorporate that in the table too...
I forgot to comment that what is multiplied by ten is not the value but the starting position in the array (a way to emulate a matrix), but anyway see my comments in previous post.
Feb 09