Re: Can this implementation of Damm algorithm be optimized?
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).
Re: usage of ref foreach with variadic functions fails with "cannot be ref"
On Saturday, 11 February 2017 at 15:02:11 UTC, error wrote:
On Saturday, 11 February 2017 at 14:43:18 UTC, rikki cattermole
wrote:
Try:
foreach(i, v; vars) {
vars[i] = ...;
}
Perfect! Thanks so much - I wish that hint was in the
documentation for variadic functions, although I guess it
suggests an inefficiency in the compiler - since there would be
an additional copy of vars[i] created in v.
Do you have a complete code example that gives your error? I
can't reproduce it (DMD v2.073.0):
int foo(T...)(T vars) {
int i = 0;
foreach(ref v ; vars) {
v = 5;
i += v;
}
return i;
}
void bar(T...)(ref T vars) {
foreach(ref v ; vars) {
v = 3;
}
}
void main() {
import std.stdio;
int x = 7;
bar(x);
writeln(foo(4,x,8.2)); // 15, no errors
}
Re: Gc collects trigger access violation exception
problem solved now. Just not use gc_setProxy.
Re: Can this implementation of Damm algorithm be optimized?
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/fiamjuhiddbzwvapl...@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.
Re: Why can't I init a new var from const var?
On 02/12/2017 12:15 AM, Random D user wrote:
I can init a variable from mutable source without defining any
constructor or assignment operators, but not if the source is const. I
would imagine the behavior to be the same with mutable and const source,
since it's just reading the source and copying it.
It works as long as your type has no mutable indirections (pointers,
array, class objects). You can't just copy an indirection from const to
mutable, because the referenced (possibly immutable) data would be
incorrectly typed as mutable.
Is there a reason for this? Or is this a bug?
I can workaround this by making copies or casting, that just creates
ugly code everywhere.
Here's an example (with dmd 2.073):
struct Foo
{
[...]
this( const Foo source )
{
buf = source.buf.dup;
}
[...]
char[] buf;
}
Foo fun(const ref Foo foo, Foo foo2)
{
Foo bar = foo; // Error: cannot implicitly
convert expression (foo) of type const(Foo) to Foo
Initializations like this don't call the constructor. Instead, they do
"copy construction" and call a "postblit function" if it's defined.
See https://dlang.org/spec/struct.html#struct-postblit
So, if you want to call a function whenever your struct gets copied, you
define a postblit function. Like so: this(this) { buf = buf.dup; }
Or if you want to do the dup-ing in specific places only, call the
constructor explicitly: Foo bar = Foo(foo);
Foo baz = foo2;// Ok, No need for constructors
or opAssign
Note that this does not call the constructor, and does not do the dup.
If you want this to do the dup, postblit is the way.
[...]
//Foo bar = Foo(foo); // This works provided there is non-const
opAssign defined.
//Foo bar = cast(Foo)foo; // This seems to work as well
I wouldn't have expected the cast to call the constructor, but
apparently it does. It's in the spec here:
https://dlang.org/spec/expression.html#CastExpression
"Casting a value v to a struct S, when value is not a struct of the same
type, is equivalent to: S(v)"
So a cast like that is really just a fancy way of calling the constructor.
This seems a bit inconsistent, though. On postblit the spec says that
copy construction happens with "the same type". The compiler apparently
sees Foo and const(Foo) as the "same type" in that context. But with the
cast, the qualifier mismatch is enough to trigger the constructor call
which is supposed to happen when the types are not the same.
return bar;
}
Foo foo;
foo = fun(foo, foo);
Re: Why can't I init a new var from const var?
On 02/11/2017 03:15 PM, Random D user wrote:
> I can init a variable from mutable source without defining any
> constructor or assignment operators, but not if the source is const. I
> would imagine the behavior to be the same with mutable and const source,
> since it's just reading the source and copying it.
>
> Is there a reason for this? Or is this a bug?
> I can workaround this by making copies or casting, that just creates
> ugly code everywhere.
Just to make sure, you don't need to define all those overloads. This is
sufficient but you have to use a different (and idiomatic construction
syntax.):
struct Foo
{
this( const(Foo) source )
{
buf = source.buf.dup;
}
void opAssign( const(Foo) source )
{
buf = source.buf.dup;
}
char[] buf;
}
Foo fun(const ref Foo foo, Foo foo2)
{
auto bar = Foo(foo);
// Foo bar = foo; // Error: cannot implicitly
convert expression (foo) of type const(Foo) to Foo
Foo baz = foo2;// Ok, No need for constructors
or opAssign
auto baz2 = const(Foo)(foo2);
Foo bar2;
bar2 = foo; // uses opAssing( const Foo ) /
opAssign( const ref Foo )
Foo bar3;
bar3 = foo2;// uses opAssign( const Foo ) /
opAssign( Foo )
Foo bar4;
bar4 = cast(const Foo)foo2; // uses opAssing( const Foo )
//Foo bar = Foo(foo); // This works provided there is non-const
opAssign defined.
//Foo bar = cast(Foo)foo; // This seems to work as well
return bar;
}
void main() {
}
When you do this:
Foo bar = foo;
There is an implicit conversion in place, which D does not allow during
construction. The idiomatic syntax is the following:
auto bar = Foo(foo);
The construction on the right-hand side is now explicit.
Likewise, prefer the following syntax:
auto baz2 = const(Foo)(foo2);
Notes:
When you want to treat lvalue sources differently from rvalue sources,
you can define the following overloads as well (note const(Foo) syntax,
which is preferred):
this( ref const(Foo) source )
{
buf = source.buf.dup;
}
void opAssign( ref const(Foo) source )
{
buf = source.buf.dup;
}
Alternatively, you can define an 'auto ref' function that automatically
takes both lvalues and rvalues (lvalue by-ref, rvalues by-move). Note
the empty template parentheses:
struct Foo
{
this()( auto ref const(Foo) source )
{
buf = source.buf.dup;
}
void opAssign()( auto ref const(Foo) source )
{
buf = source.buf.dup;
}
char[] buf;
}
Ali
Re: Can this implementation of Damm algorithm be optimized?
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.
Why can't I init a new var from const var?
I can init a variable from mutable source without defining any
constructor or assignment operators, but not if the source is
const. I would imagine the behavior to be the same with mutable
and const source, since it's just reading the source and copying
it.
Is there a reason for this? Or is this a bug?
I can workaround this by making copies or casting, that just
creates ugly code everywhere.
Here's an example (with dmd 2.073):
struct Foo
{
this( Foo source )
{
buf = source.buf.dup;
}
this( const Foo source )
{
buf = source.buf.dup;
}
this( const ref Foo source )
{
buf = source.buf.dup;
}
void opAssign( Foo source )
{
buf = source.buf.dup;
}
void opAssign( const Foo source )
{
buf = source.buf.dup;
}
void opAssign( const ref Foo source )
{
buf = source.buf.dup;
}
char[] buf;
}
Foo fun(const ref Foo foo, Foo foo2)
{
Foo bar = foo; // Error: cannot
implicitly convert expression (foo) of type const(Foo) to Foo
Foo baz = foo2;// Ok, No need for
constructors or opAssign
Foo baz2 = cast(const Foo)foo2; // Error: cannot
implicitly convert expression (Foo(null).this(foo2)) of type
const(Foo) to Foo
Foo bar2;
bar2 = foo; // uses opAssing( const
Foo ) / opAssign( const ref Foo )
Foo bar3;
bar3 = foo2;// uses opAssign( const
Foo ) / opAssign( Foo )
Foo bar4;
bar4 = cast(const Foo)foo2; // uses opAssing( const
Foo )
//Foo bar = Foo(foo); // This works provided there is
non-const opAssign defined.
//Foo bar = cast(Foo)foo; // This seems to work as well
return bar;
}
Foo foo;
foo = fun(foo, foo);
Re: Can this implementation of Damm algorithm be optimized?
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 TreeFuncPer CallsTimeTimeCall 1200 1281989 1281989 0 char damm.checkDigit(immutable(char)[]) 1200 1146308 1146308 0 char damm.checkDigit2(immutable(char)[])
Re: Can this implementation of Damm algorithm be optimized?
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;
}
Re: Can this implementation of Damm algorithm be optimized?
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.
Re: Can this implementation of Damm algorithm be optimized?
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.
Re: usage of ref foreach with variadic functions fails with "cannot be ref"
On Saturday, 11 February 2017 at 14:43:18 UTC, rikki cattermole
wrote:
Try:
foreach(i, v; vars) {
vars[i] = ...;
}
Perfect! Thanks so much - I wish that hint was in the
documentation for variadic functions, although I guess it
suggests an inefficiency in the compiler - since there would be
an additional copy of vars[i] created in v.
Re: Why do static arrays affect executable size?
Thanks for the clarifications.
Re: Why do static arrays affect executable size?
On Saturday, 11 February 2017 at 00:16:04 UTC, sarn wrote: If you explicitly initialise the array to all 0.0, you should see it disappear from the binary. I was actually wondering whether initialisation would make a difference, so thank you for this. Bastiaan.
Re: usage of ref foreach with variadic functions fails with "cannot be ref"
On 12/02/2017 3:41 AM, error wrote:
I'm making a serializer that has a variadic write method that takes
arbitrary params
and serializes them; I want to do the same thing with a read method (
pass in your
params by ref, and it populates them with data ) - however, I run into
a compiler
error - "cannot be ref" in the foreach statement... Anyone know a
workaround for this? Is this a bug, or by design?
Simplified example:
void populateVars(T...)(T vars){
// Generates "cannot be ref" compiler error:
foreach(ref v; vars){
// Populate v with some data here...
}
}
Try:
foreach(i, v; vars) {
vars[i] = ...;
}
usage of ref foreach with variadic functions fails with "cannot be ref"
I'm making a serializer that has a variadic write method that
takes arbitrary params
and serializes them; I want to do the same thing with a read
method ( pass in your
params by ref, and it populates them with data ) - however, I
run into a compiler
error - "cannot be ref" in the foreach statement... Anyone know
a workaround for this? Is this a bug, or by design?
Simplified example:
void populateVars(T...)(T vars){
// Generates "cannot be ref" compiler error:
foreach(ref v; vars){
// Populate v with some data here...
}
}
Re: Can this implementation of Damm algorithm be optimized?
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.
