Re: Compiletime Vs Runtime bencmarks
On Monday, 17 August 2015 at 22:01:32 UTC, John Colvin wrote: On Monday, 17 August 2015 at 17:48:22 UTC, D_Learner wrote: On Monday, 17 August 2015 at 14:52:18 UTC, Edwin van Leeuwen wrote: [...] The surprisingly, the D-profiler gives plausible results:- Algorithm1 2921 int rtime_pre.bm_rmatch (runtime ) 2122 int ctime_pre.bm_cmatch (compiletime ) 1317int rtime_pre.bmh_rmatch (runtime ) 1099int ctime_pre.bmh_cmatch (compiletime ) 3959 int rtime_pre.ag_rmatch (runtime ) 2688 pure int ctime_pre.ag_cmatch (compiletime ) This suggests that my timer design has some flaw ;) std.datetime.StopWatch is the easiest way to do timing manually, or just use std.datetime.benchmark My code already uses std.datetime.StopWatch , but I get results which are no match to the D profiler's. Though am not searching for exact, but theyy must be comparable atleast.
Re: Compiletime Vs Runtime bencmarks
On Monday, 17 August 2015 at 22:01:32 UTC, John Colvin wrote: On Monday, 17 August 2015 at 17:48:22 UTC, D_Learner wrote: On Monday, 17 August 2015 at 14:52:18 UTC, Edwin van Leeuwen wrote: [...] The surprisingly, the D-profiler gives plausible results:- Algorithm1 2921 int rtime_pre.bm_rmatch (runtime ) 2122 int ctime_pre.bm_cmatch (compiletime ) 1317int rtime_pre.bmh_rmatch (runtime ) 1099int ctime_pre.bmh_cmatch (compiletime ) 3959 int rtime_pre.ag_rmatch (runtime ) 2688 pure int ctime_pre.ag_cmatch (compiletime ) This suggests that my timer design has some flaw ;) std.datetime.StopWatch is the easiest way to do timing manually, or just use std.datetime.benchmark My code already uses std.datetime.StopWatch , but I get results which are no match to the D compilers.
Compiletime Vs Runtime bencmarks
Hello everyone . I need advice on my first D-project . I have uploaded it at :- https://bitbucket.org/mrjohns/matcher/downloads IDEA : Benchmarking of 3 runtime algorithms and comparing them to their compile-time variants. The only difference between these is that for the compile time-ones, the lookup tables (i.e. Arrays bmBc, bmGs, and suffixes ) must be computed at compile time( I currently rely on CTFE ) . While for the runtime-ones the lookup tables are computed on runtime. NB : The pattern matching algorithms themselves need not be executed at compile-time, only the lookup tables.Having stated this the algorithms which run on known( compile-time computed) tables must be faster than the ones which have to compute them at runtime. My results seem to show something different, only the first pair( BM_Runtime and BM_Compile-time) yields admissible results, the other two pair give higher execution time for the compile-time variants. I think am missing something here. Please help. Current Results for the pattern=GCAGAGAG are as below :- BM_Runtime = 366 hnsecs position= 513 BM_Compile-time = 294 hnsecs position =513 BMH_Runtime = 174 hnsecs position= 513 BMH_Compile-time= 261 hnsecs position= 513 AG_Run-time = 258 hnsecsposition= 513 AG_Compile-time = 268 hnsecsposition= 513 Running the code : dmd -J. matcher.d inputs.d rtime_pre.d ctime_pre.d numactl --physcpubind=0 ./matcher I would appreciate your suggestions. Regards,
Re: Compiletime Vs Runtime bencmarks
On Monday, 17 August 2015 at 14:52:18 UTC, Edwin van Leeuwen wrote: On Monday, 17 August 2015 at 14:43:35 UTC, D_Learner wrote: Hello everyone . I need advice on my first D-project . I have uploaded it at :- Current Results for the pattern=GCAGAGAG are as below :- BM_Runtime = 366 hnsecs position= 513 BM_Compile-time = 294 hnsecs position =513 BMH_Runtime = 174 hnsecs position= 513 BMH_Compile-time= 261 hnsecs position= 513 AG_Run-time = 258 hnsecsposition= 513 AG_Compile-time = 268 hnsecsposition= 513 Running the code : dmd -J. matcher.d inputs.d rtime_pre.d ctime_pre.d numactl --physcpubind=0 ./matcher Hi, What happens if you run each algorithm many (say 10) times. The current times seem to short to be reliable (variation in runtimes would be too great). Regards, Edwin The surprisingly, the D-profiler gives plausible results:- Algorithm1 2921 int rtime_pre.bm_rmatch (runtime ) 2122 int ctime_pre.bm_cmatch (compiletime ) 1317int rtime_pre.bmh_rmatch (runtime ) 1099int ctime_pre.bmh_cmatch (compiletime ) 3959 int rtime_pre.ag_rmatch (runtime ) 2688 pure int ctime_pre.ag_cmatch (compiletime ) This suggests that my timer design has some flaw ;)
Re: Compiletime Vs Runtime bencmarks
On Monday, 17 August 2015 at 14:52:18 UTC, Edwin van Leeuwen wrote: On Monday, 17 August 2015 at 14:43:35 UTC, D_Learner wrote: Hello everyone . I need advice on my first D-project . I have uploaded it at :- Current Results for the pattern=GCAGAGAG are as below :- BM_Runtime = 366 hnsecs position= 513 BM_Compile-time = 294 hnsecs position =513 BMH_Runtime = 174 hnsecs position= 513 BMH_Compile-time= 261 hnsecs position= 513 AG_Run-time = 258 hnsecsposition= 513 AG_Compile-time = 268 hnsecsposition= 513 Running the code : dmd -J. matcher.d inputs.d rtime_pre.d ctime_pre.d numactl --physcpubind=0 ./matcher Hi, What happens if you run each algorithm many (say 10) times. The current times seem to short to be reliable (variation in runtimes would be too great). Regards, Edwin Thyanks, I havent tried that. So it seems you suggest I must fucus on average times. Will try it , the above results are from a single run (no looping), but after executing the program several times I realised that the 1st two seem ok(relatively stable results for same pattern), but the other pair give higher performance for the run-time versions.
Re: using memset withing a pure function
On Saturday, 15 August 2015 at 01:13:02 UTC, Adam D. Ruppe wrote: On Saturday, 15 August 2015 at 01:09:15 UTC, D_Learner wrote: When writting a pure fucntion involving C non pure functions like memcpy() and memset() Those functions are pure already, and marked so in the newest dmd (and I think older ones too, though I haven't confirmed. Your code compiled out of the box for me. BTW D also has some syntax sugar for them: arr[start .. end] = 0; // memset those bounds to 0 arr[start .. end] = arr2[start .. end]; // memcpy You could be surprised am still trying to get my head around this. Considering the code :- memcpy(skip[0], skip[0]+shift, (m-shift)*(int.sizeof)); memset(skip[0]+(m-shift),0, shift*(int.sizeof)) I was thinking conversion would be :- skip[0 .. size-1] = skip[shift .. size-1 ]; //For the memcpy(); skip[0 .. size-1] = 0;//For memset() But this doesn't seem to work for me as dmd(v2.066.1) gives the error slice [8..7] exceeds array bounds [0..8] .Sure am missing something.
Re: using memset withing a pure function
On Saturday, 15 August 2015 at 18:49:15 UTC, anonymous wrote: On Saturday, 15 August 2015 at 18:04:30 UTC, D_Learner wrote: [...] Those two slices have different lengths (when shift != 0). They must have equal lengths, and they must not overlap. [...] Am now sorted. Thanks, your workout simplifies everything
Re: Compiletime Table
On Friday, 14 August 2015 at 20:48:43 UTC, Adam D. Ruppe wrote: On Friday, 14 August 2015 at 20:40:13 UTC, D_Learner wrote: Perhaps I have to get myself a copy. you should! There's a lot of little tips and tricks in there. Am currently looking at your Dconf2015 talk . My blasphemous talk as I like to call it :) There's a bit in the video where i went off script and started demoing and it wasn't shown. It was just this program fyi: https://github.com/adamdruppe/inspector not that magical but kinda cool in how simple the code was able to be. Just downloaded the demo, cheers!
Re: Compiletime Table
On Thursday, 13 August 2015 at 19:26:12 UTC, Adam D. Ruppe wrote: On Thursday, 13 August 2015 at 19:13:55 UTC, D_Learner wrote: [...] It is currently not possible to build an associative array at compile time and keep it as a runtime table due to the implementation. [...] Am aware you have published a book on D. Perhaps I have to get myself a copy. Am currently looking at your Dconf2015 talk . Thanks for your advice.
Re: Compiletime Table
On Thursday, 13 August 2015 at 19:54:18 UTC, anonymous wrote:
On Thursday, 13 August 2015 at 19:13:55 UTC, D_Learner wrote:
[...]
I think you may have some fundamental misunderstandings
regarding CTFE, templates, etc. Your code seems to be half-way
between a template-based and a CTFE-based solution.
The simple way to do compile-time computation in D is CTFE
(Compile Time Function Evaluation). That is, you write a pure
function that can be evaluated both at run-time and at
compile-time. CTFE doesn't need template parameters.
Here's some code that should do the same as yours and is
compatible with CTFE:
import std.conv: to;
import std.stdio;
int[char] calculatebmBc(string pattern) pure
{
const int size = to!int(pattern.length);
int[char] result;
foreach(i; 0 .. size - 1)
{
result[pattern[i]] = to!int(size - i - 1);
}
return result;
}
void main()
{
auto bmBc = calculatebmBc(GCAGAGAG);
enum bmBcTable = calculatebmBc(GCAGAGAG);
}
The key is that calculatebmBc is pure, i.e. it doesn't read or
write any module-level mutables.
I touched some things here and here I didn't like that are not
related to purity/CTFE.
Adam D. Ruppe already mentioned an issue with associative
arrays: This doesn't work:
static foo = calculatebmBc(GCAGAGAG);
It's annoying, but if you need that you have to use some other
data structure. See Adam's post.
Thanks so much for the advice, it works fine. Just experimented
with the code . I had no idea about it. My mind had the some
pre-occupation that compile-time execution is only achievable
through templates. Had no idea about pure functions...awesone ,
code. Thanks again for the clear explanation.
using memset withing a pure function
When writting a pure fucntion involving C non pure functions like
memcpy() and memset() , what could be the way around? Should I
re-write these and make them pure?
The code am converting is as below :-
int ag_cmatch(const string pattern, const string text,
int[char] bmBc , int[size] bmGs ) pure { //Start of AG search
algorithm
int i,j,k , s, shift;
int[size] skip;
int[size] suff;
int m = to!int(pattern.length);
int n = to!int(text.length);
int position = -1;
/* Preprocessing */
memset(skip[0], 0, m* int.sizeof); // Initialise skip table
/* searching */
j = 0;
while(j=n-m){
i=m-1;
while( i = 0){ // Start inner while
k = skip[i];
s = suff[i];
if( k 0)
if( k s){
//writeln( Int Size 3 , int.sizeof);
if(i+1 == s)
i = (-1);
else {
i -=s;
//writeln(Innner while loop
.Found... );
break;
}
}
else{
i-=k;
if( k s ){
// writeln(Innner while loop .Found 1
... );
//getchar();
break;
}
}
else {
if ( pattern[i] == text[i+j]){
--i;
//writeln(Innner while loop .Found 2
);
}
else
break;
}
}// End inner while
if ( i 0){
//writeln( AG Pattern found at :, j);
position = j;//Added for display / reporting
//getchar();
// Manually added to cause a pattern found stop(Not in
documentation)
skip[m-1] = m;
shift = bmGs[0];
break;
}
else{
skip[ m-1 ] = m -1 -i;
shift = bmGs[i] (bmBc[text[i+j]] - m + 1 + i) ? bmGs[i] :
(bmBc[text[i+j]] - m + 1 + i ) ;
}
j+=shift;
// writeln( j Before memcpy== : , j);
memcpy(skip[0], skip[0]+shift,
(m-shift)*(int.sizeof));
memset(skip[0]+(m-shift),0, shift*(int.sizeof));
}//End outer while
return position ;
}//End AG search
Re: using memset withing a pure function
On Saturday, 15 August 2015 at 01:13:02 UTC, Adam D. Ruppe wrote: On Saturday, 15 August 2015 at 01:09:15 UTC, D_Learner wrote: When writting a pure fucntion involving C non pure functions like memcpy() and memset() Those functions are pure already, and marked so in the newest dmd (and I think older ones too, though I haven't confirmed. Your code compiled out of the box for me. BTW D also has some syntax sugar for them: arr[start .. end] = 0; // memset those bounds to 0 arr[start .. end] = arr2[start .. end]; // memcpy Well, the actual error I got is : Error: memset cannot be interpreted at compile time, because it has no available source code . I seems to suggest I miss the actual code.
Re: Structs and compiletime evaluation
On Thursday, 13 August 2015 at 12:21:44 UTC, Rikki Cattermole
wrote:
On Thursday, 13 August 2015 at 12:07:48 UTC, D_Learner wrote:
I am having this struct :-
struct COMPILETIME_BM_PRE
{
void initialisebmBc(S,C,I,int k)( const S pattern ,ref
I[C] bmBc){
static if ( k ASIZE ){
bmBc[ALPHABET[k]] = size;
initialisebmBc!(S,C,I,k+1)( pattern ,bmBc);
}
}
void initialisebmBc(S,C,I,int k : ASIZE)( const S
pattern ,ref I[C] bmBc){}
[...]
No it wouldn't be. It's declared for runtime usage. Not compile
time.
Also bmBc isn't declared as an enum (can't be in fact, bug with
AA's). So even if bmh was accessible, bmBc isn't.
Thanks Rikki, but what do you mean by AA's ?
Structs and compiletime evaluation
I am having this struct :-
struct COMPILETIME_BM_PRE
{
void initialisebmBc(S,C,I,int k)( const S pattern ,ref I[C]
bmBc){
static if ( k ASIZE ){
bmBc[ALPHABET[k]] = size;
initialisebmBc!(S,C,I,k+1)( pattern ,bmBc);
}
}
void initialisebmBc(S,C,I,int k : ASIZE)( const S pattern
,ref I[C] bmBc){}
void calculatebmBc(S,C,I,int i)( const S pattern ,ref I[C]
bmBc)
{
static if ( i size -1 )
bmBc[pattern[i]] = size -i-1;
calculatebmBc!(S,C,I,i+1)(pattern ,bmBc);
}
I[C] preBmBc(S ,C,I)( const S pattern ,ref I[C] bmBc){
this.initialisebmBc!(S,C,I,0)( pattern ,bmBc);
this.calculatebmBc!(S,C,I,0)(pattern ,bmBc);
return bmBc;
}
}
In another module I use the struct as below :-
int[char] bmBc;
COMPILETIME_BM_PRE bmh ;
enum bmBc1 = bmh.preBmBc!(string ,char,int)( pattern , bmBc);
On last line , I get the error message : `Error: variable bmh
cannot be read at compile time` , yet I thought this value would
be evaluated at compiletime.
Compiletime Table
I was wondering how I could change the code below such the `bmBc`
is computed at compile time . The one below works for runtime but
it is not ideal since I need to know the `bmBc` table at
compile-time . I could appreciate advice on how I could improve
on this.
import std.conv:to;
import std.stdio;
int [string] bmBc;
immutable string pattern = GCAGAGAG;
const int size = to!int(pattern.length);
struct king {
void calculatebmBc(int i)()
{
static if ( i size -1 )
bmBc[to!string(pattern[i])]=to!int(size-i-1);
//bmBc[pattern[i]] ~= i-1;
calculatebmBc!(i+1)();
}
void calculatebmBc(int i: size-1)() {
}
}
void main(){
king myKing;
const int start = 0;
myKing.calculatebmBc!(start)();
//1. enum bmBcTable = bmBc;
}
Re: Compiletime Table
On Thursday, 13 August 2015 at 19:26:12 UTC, Adam D. Ruppe wrote:
On Thursday, 13 August 2015 at 19:13:55 UTC, D_Learner wrote:
I was wondering how I could change the code below such the
`bmBc` is computed at compile time .
It is currently not possible to build an associative array at
compile time and keep it as a runtime table due to the
implementation.
However, looking at your code, you don't need a full AA... the
key is a single char, right?
Do something like this:
int[128] bmBc = calculate(); //
And then a line like this should work to set it in the
calculate function:
bmBc[pattern[i]] = i-1;
Adjust this code to fit you:
int[128] a = calc();
enum string pattern = abc;
int[128] calc() {
int[128] a; // local copy to work on as we build
a[pattern[0]] = 0;
return a; // return the completed table
}
This works because individual characters have a numeric value.
If they are all A-Z, you can easily fit them in a small array
and access them even faster than an associative array (doesn't
even have to be full size 128 if the only keys are the letters).
And these can be built at CTFE and stored in the program's data
segment.
Thanks, the 128 is fine since I was considering the whole ASCII
character set . I was a bit skeptical of writing the code in that
manor though since I have to still compare runtime and
compiletime implementation performance(benchmarks ). That is why
my code seemed to mimic templating . Maybe the question would
then be, how do I force this function to be fully executed at
compiletime and later make it be executed at runntime ?
