11-Jan-2013 05:43, Timon Gehr пишет:
> On 01/10/2013 08:52 PM, Dmitry Olshansky wrote:
[snip]
>>
>> Cool! I'd love to take even the very preliminary peek at the speed
>> profile of this CTFE engine.
>>
>> If you are interested I'd love to test a small (the code though contains
>> a lot of static data) CTFE benchmark that is the bottleneck in the
>> compilation of current ctRegex.
>>
>> See the attachment here:
>> http://d.puremagic.com/issues/show_bug.cgi?id=7442
>>
>> would be nice to see some rough numbers for this vs DMD.
>>
>
> I'll let you know as soon as the example runs. Currently this is blocked
> by the missing implementation for the following language features:
>
> - import declarations
> - UFCS
> - Optional parens on function calls
> - Struct literals
> - Static struct data
> - debug declarations
> - Some of the built-in array operations
> - Missing object.d (no string, size_t, hash_t alias.)
> - (static) foreach
> - __ctfe
>

I guess that core.bitop intrinsics too. Either way, thanks in advance.

> I will prioritize those features. Except import declarations, they are
> mostly easy to implement, but I haven't gotten around to them yet.
>
> For the meantime, maybe these quick measurements are somewhat useful:
>

They truly are. As I've been long wondering that CTFE could be quite fast if it wasn't for it's current architecture in DMD. Just needed the hard data to go by.

> int[] erathos(int x){
>      bool[] p;
>      for(int i=0;i<=x;i++) p~=true;
>      for(int i=3;i*i<=x;i+=2){
>          if(p[i]) for(int k=i*i;k<=x;k=k+i) p[k]=false;
>      }
>      int[] r;
>      if(x>=2) r~=2;
>      for(int i=3;i<=x;i+=2) if(p[i]) r~=i;
>      return r;
> }
>
> pragma(msg, "erathos: ",erathos(40000).length);
>
>
> The frontend (32-bit dmd build, without -inline, otherwise DMD ICEs):
> $ time ./d erathos.d
> erathos: 4203U
>
> real    0m0.077s
> user    0m0.076s
> sys    0m0.000s
>
>
> DMD 2.060 (64 bit):
> $ time dmd -o- erathos.d
> erathos: 4203u
>
> real    0m2.594s
> user    0m0.716s
> sys    0m1.696s
>
>
> ...
>
> pragma(msg, "erathos: ",erathos(400000)); // (that is one 0 more)
>
> The frontend:
> erathos: 33860U
>
> real    0m0.662s
> user    0m0.660s
> sys    0m0.000s
>
> DMD: brings down the machine
>
> pragma(msg, "erathos: ",erathos(4000000)); // (yet another 0 more)
>
> The frontend:
> erathos: 283146U
>
> real    0m6.867s
> user    0m6.832s
> sys    0m0.016s
>
> // pragma(msg, "erathos: ",erathos(4000000));
> void main(){
>      import std.stdio;
>      writeln(erathos(4000000).length);
> }
>
> $ dmd -O -release -inline -noboundscheck erathos.d && time ./erathos
> dmd: module.c:829: void Module::semantic3(): Assertion `semanticstarted
> == 2' failed.

I bet this one was fixed in 2.061, I've recently seen the similar bug as resolved "works for me".

> (I'll see if it also fails with DMD 2.061.)
>
> $ dmd -O -release -noboundscheck erathos.d && time ./erathos
> 283146
>
> real    0m0.144s
> user    0m0.132s
> sys    0m0.008s
>

> So CTFE in the front end seems to be ~50 times slower than a optimized
> DMD build of the same code in this case. But note that it is powered by
> a simple-minded bytecode interpreter I hacked together mostly during two
> weekends.

Yes, yes and yes! Simple bytecode interpreter is what I've been waiting for :)

> (the array append is the one from druntime) A lot more is
> possible. I guess it is already fast enough to power std.regex.

Sure and a simple threaded-code interpreter should make it fly (when D has e.g. explicit tail call).

-- 
Dmitry Olshansky

On Fri, Jan 11, 2013 at 08:47:19AM +0100, deadalnix wrote:
> On Thursday, 10 January 2013 at 22:28:46 UTC, H. S. Teoh wrote:
> >On Thu, Jan 10, 2013 at 11:18:07PM +0100, Era Scarecrow wrote:
> >>On Thursday, 10 January 2013 at 22:02:17 UTC, Dmitry Olshansky wrote:
> >>>+ user defined implicit conversion so that AALiteral(K,V)
> >>>--*implicitly*!--> AA!(K,V)
> >>>
> >>>
> >>>The other use case for user-defined implicit conversion were already outlined before so I hope it will make its way in one day.
> >>
> >> I thought I heard talk of possibly moving AA's to a library
> >>implementation rather than a built in feature (Still 'built in'
> >>technically).
> >
> >That's my plan, and Andrei's hope. But it's not going to be easy. The current AA implementation is split between object_.d and aaA.d in druntime, with bits scattered throughout the compiler. Cleaning all of that up is going to be a big job.
> >
> 
> You may want to look at this : http://preshing.com/20130107/this-hash-table-is-faster-than-a-judy-array
> 
> Additionally, can you show me what you have so far ? I'd be interested in using it directly for SDC without using the existing one at all.

https://github.com/quickfur/New-AA-implementation

It's basically just a refactoring of the current AA code to hoist it into object_.d; I didn't introduce any new algorithms or data structures.


T

-- 
This is a tpyo.