On 2 April 2015 at 08:15, Martin Nowak via Digitalmars-d <digitalmars-d@puremagic.com> wrote:
> On 04/01/2015 10:31 PM, novice2 wrote:
>> Can DMD compiler do it itself, as one of optimizations?
>
> You could do it as part of LTO or whole program optimization.
> It requires another compiler/linker phase, so it's not easy to achieve,
> maybe the LDC/GDC people have LTO running?
>
> GCC5 comes with a big announcement about devirtualization. https://www.gnu.org/software/gcc/gcc-5/changes.html#general

It is impossible to do a good job. There are 2 conditions that break
most opportunities that the compiler may have to improve this:
1) The class is a pointer (duh, in D, all classes are pointers, so
that condition is implicit).
2) That DLL's exist.

If a DLL may exist, and a class is a pointer (it is), sourced from an
'impure' location, then it is impossible for the compiler to generally
do anything at all about final.
It may theoretically be able to do something in the case where the
class is proofably contained within a 'scope' confined space/function,
but that particular case is almost mutually exclusive with cases where
polymorphism is actually useful in the first place, so it's not really
practical. I also imagine the complexity in the compiler would be off
the charts.

Basically, if it is _possible_ for a class pointer to come in contact with dynamically loaded code, the compiler must conservatively abandon any attempt to optimise.

virtual by default is completely wrong for D.

And don't say 'speculative' devirtualisation. What an abomination! Just fix the problem; don't have every function be virtual in the first place!

On Thursday, 2 April 2015 at 08:32:13 UTC, anonymous wrote:
> It would be nice to have such a good matrix multiplication in
> Phobos but I think there are more important things to work on
> (GC, AA, ...),

I'm not asking for a linear algebra library in phobos, although we need one in dub and should consider having one in Phobos at some point too.
But it would be nice if std.numeric came with a multiply(T)(T[][] a, T[][] b, T[][] result) to complement dotProduct and the built-in vector ops.
As you've seen dotProduct set us far ahead of C.

> Dstep + cblas.h works quite well although code calling it
> involves pointers :)

How hard would it be to turn that into a lib.

On Thursday, 2 April 2015 at 09:09:04 UTC, Martin Nowak wrote:
> I'm not asking for a linear algebra library in phobos, although we need one in dub and should consider having one in Phobos at some point too.
> But it would be nice if std.numeric came with a multiply(T)(T[][] a, T[][] b, T[][] result) to complement dotProduct and the built-in vector ops.
> As you've seen dotProduct set us far ahead of C.

Sounds good:
- a matrix multiplication in phobos that is faster than a naive
implementation but does not try to beat BLAS gemm.
- a dub LA library around BLAS. There is
http://code.dlang.org/packages/cblas but it seems to be not much
more than dstep + cblas.h

> How hard would it be to turn that into a lib.
Don't know, I perhaps try.
I have a working prototype of a BFGS non-linear optimizer
currently calling BLAS via array.ptr and the vague plan to make
it opensource. If that ever happens, a LA library around BLAS
would be a great co-product.

On Thursday, 2 April 2015 at 09:06:52 UTC, Manu wrote:
> On 2 April 2015 at 08:15, Martin Nowak via Digitalmars-d
> <digitalmars-d@puremagic.com> wrote:
>> On 04/01/2015 10:31 PM, novice2 wrote:
>>> Can DMD compiler do it itself, as one of optimizations?
>>
>> You could do it as part of LTO or whole program optimization.
>> It requires another compiler/linker phase, so it's not easy to achieve,
>> maybe the LDC/GDC people have LTO running?
>>
>> GCC5 comes with a big announcement about devirtualization.
>> https://www.gnu.org/software/gcc/gcc-5/changes.html#general
>
> It is impossible to do a good job. There are 2 conditions that break
> most opportunities that the compiler may have to improve this:
> 1) The class is a pointer (duh, in D, all classes are pointers, so
> that condition is implicit).
> 2) That DLL's exist.
>
> If a DLL may exist, and a class is a pointer (it is), sourced from an
> 'impure' location, then it is impossible for the compiler to generally
> do anything at all about final.
> It may theoretically be able to do something in the case where the
> class is proofably contained within a 'scope' confined space/function,
> but that particular case is almost mutually exclusive with cases where
> polymorphism is actually useful in the first place, so it's not really
> practical. I also imagine the complexity in the compiler would be off
> the charts.
>
> Basically, if it is _possible_ for a class pointer to come in contact
> with dynamically loaded code, the compiler must conservatively abandon
> any attempt to optimise.
>
> virtual by default is completely wrong for D.
>
> And don't say 'speculative' devirtualisation. What an abomination!
> Just fix the problem; don't have every function be virtual in the
> first place!

+1

Even an escape would be useful so one can do this:

final class Hack {
    virtual void func() {}
}

It would then be trivial to stick a final in front of the class.

It would also be required to declare final when instantiating the class, to work with third-party libraries that don't use final, i.e.

auto klass = new final Class();


I'm not a language developer and I don't know D that well yet so I'll stop there before I embarrass myself too much! :D

bye,
lobo

On Thu, 02 Apr 2015 11:00:12 +0000
lobo via Digitalmars-d <digitalmars-d@puremagic.com> wrote:

> On Thursday, 2 April 2015 at 09:06:52 UTC, Manu wrote:
> > On 2 April 2015 at 08:15, Martin Nowak via Digitalmars-d <digitalmars-d@puremagic.com> wrote:
> >> On 04/01/2015 10:31 PM, novice2 wrote:
> >>> Can DMD compiler do it itself, as one of optimizations?
> >>
> >> You could do it as part of LTO or whole program optimization.
> >> It requires another compiler/linker phase, so it's not easy to
> >> achieve,
> >> maybe the LDC/GDC people have LTO running?
> >>
> >> GCC5 comes with a big announcement about devirtualization. https://www.gnu.org/software/gcc/gcc-5/changes.html#general
> >
> > It is impossible to do a good job. There are 2 conditions that
> > break
> > most opportunities that the compiler may have to improve this:
> > 1) The class is a pointer (duh, in D, all classes are pointers,
> > so
> > that condition is implicit).
> > 2) That DLL's exist.
> >
> > If a DLL may exist, and a class is a pointer (it is), sourced
> > from an
> > 'impure' location, then it is impossible for the compiler to
> > generally
> > do anything at all about final.
> > It may theoretically be able to do something in the case where
> > the
> > class is proofably contained within a 'scope' confined
> > space/function,
> > but that particular case is almost mutually exclusive with
> > cases where
> > polymorphism is actually useful in the first place, so it's not
> > really
> > practical. I also imagine the complexity in the compiler would
> > be off
> > the charts.
> >
> > Basically, if it is _possible_ for a class pointer to come in
> > contact
> > with dynamically loaded code, the compiler must conservatively
> > abandon
> > any attempt to optimise.
> >
> > virtual by default is completely wrong for D.
> >
> > And don't say 'speculative' devirtualisation. What an
> > abomination!
> > Just fix the problem; don't have every function be virtual in
> > the
> > first place!
> 
> +1
> 
> Even an escape would be useful so one can do this:
> 
> final class Hack {
>      virtual void func() {}
> }
> 
> It would then be trivial to stick a final in front of the class.
> 
> It would also be required to declare final when instantiating the class, to work with third-party libraries that don't use final, i.e.
> 
> auto klass = new final Class();
> 
> 
> I'm not a language developer and I don't know D that well yet so I'll stop there before I embarrass myself too much! :D
> 
> bye,
> lobo
> 

final class Hack {
    virtual void func() {}
}

I do not see how this would help?

If you make class Hack final, you can not use inheritence anymore so having virtual void func() does not make sense to me.

class Hack {
final:
    // some final methods
    virtual void func() {}
}

makes more sense ;)

On Thursday, 2 April 2015 at 09:06:52 UTC, Manu wrote:
> virtual by default is completely wrong for D.
>
> And don't say 'speculative' devirtualisation. What an abomination!
> Just fix the problem; don't have every function be virtual in the
> first place!

I'm not sure why you don't use struct in the first place ?

On 1 April 2015 at 04:17, weaselcat via Digitalmars-d <digitalmars-d@puremagic.com> wrote:
> On Tuesday, 31 March 2015 at 23:53:07 UTC, weaselcat wrote:
>>
>> On Tuesday, 31 March 2015 at 18:20:05 UTC, cym13 wrote:
>>>
>>> I found this repository (reddit!) that hosts common benchmarks for many languages such as D, Nim, Go, python, C, etc... It uses only standard structures not to influence the benchmark.
>>>
>>> https://github.com/kostya/benchmarks
>>
>>
>> dmd in benchmark => worthless
>> there really needs to be a big red warning that dmd is just the reference
>> implementation and use LDC/GDC for performance.
>
>
> all this benchmark made me realize is that other languages and compilers are dog slow.
>
> Removed everything except ruby, crystal, C, CPP, nim, and D(dmd and ldc), and go to save myself time. The rust version the code is for is outdated, so I couldn't do rust.
>

[snip]

Out of curiousity, which version of GDC are you using there?  Looking at the results published on github look worrying, given that they used an outdated (by our community's standards) version of Phobos with GDC (2.058, if memory serves well).  If more recent versions (DMD 2.067, LDC 0.15) are behind by a second or more, that might suggest that somewhere, something went horribly wrong in the library.

Iain.

On 2 April 2015 at 00:15, Martin Nowak via Digitalmars-d <digitalmars-d@puremagic.com> wrote:
> On 04/01/2015 10:31 PM, novice2 wrote:
>> Can DMD compiler do it itself, as one of optimizations?
>
> You could do it as part of LTO or whole program optimization.
> It requires another compiler/linker phase, so it's not easy to achieve,
> maybe the LDC/GDC people have LTO running?
>
> GCC5 comes with a big announcement about devirtualization. https://www.gnu.org/software/gcc/gcc-5/changes.html#general

I've always said: Use LTO at your own risk.  It has been broken for months at a time because I simply do not have time to give it the TLC it needs.  I expect that devirtualisation capabilities to be a little more limiting than advertised by GCC, as you do not get these sorts of optimisations for free (may need some extra support from respective frontends).

Regards
Iain

On Thursday, 2 April 2015 at 21:55:59 UTC, Iain Buclaw wrote:
> On 1 April 2015 at 04:17, weaselcat via Digitalmars-d
> <digitalmars-d@puremagic.com> wrote:
>> On Tuesday, 31 March 2015 at 23:53:07 UTC, weaselcat wrote:
>>>
>>> On Tuesday, 31 March 2015 at 18:20:05 UTC, cym13 wrote:
>>>>
>>>> I found this repository (reddit!) that hosts common benchmarks for many
>>>> languages such as D, Nim, Go, python, C, etc... It uses only standard
>>>> structures not to influence the benchmark.
>>>>
>>>> https://github.com/kostya/benchmarks
>>>
>>>
>>> dmd in benchmark => worthless
>>> there really needs to be a big red warning that dmd is just the reference
>>> implementation and use LDC/GDC for performance.
>>
>>
>> all this benchmark made me realize is that other languages and compilers are
>> dog slow.
>>
>> Removed everything except ruby, crystal, C, CPP, nim, and D(dmd and ldc),
>> and go to save myself time. The rust version the code is for is outdated, so
>> I couldn't do rust.
>>
>
> [snip]
>
> Out of curiousity, which version of GDC are you using there?  Looking
> at the results published on github look worrying, given that they used
> an outdated (by our community's standards) version of Phobos with GDC
> (2.058, if memory serves well).  If more recent versions (DMD 2.067,
> LDC 0.15) are behind by a second or more, that might suggest that
> somewhere, something went horribly wrong in the library.
>
> Iain.

gdc (GCC) 4.9.2
I'm not sure how to get GDC to show which D version it's based on - but I think it's 2.065. I'm using the latest one available in Arch repos.

On Tuesday, 31 March 2015 at 18:20:05 UTC, cym13 wrote:
> I found this repository (reddit!) that hosts common benchmarks for many languages such as D, Nim, Go, python, C, etc... It uses only standard structures not to influence the benchmark.
>
> https://github.com/kostya/benchmarks

Thanks for this.

BTW, some of these benchmarks were taken from attractivechaos here.  He seems to be working in bioinformatics and does not consider himself a programmer by profession.  But has written some libraries others use, and is clearly bright and thoughtful.  He is pro-D and sad people have not recognized its qualities.

https://attractivechaos.wordpress.com/

From 2010:
"Although I do not use D, I always see it as one of the most attractive programming languages, smartly balancing efficiency, simplicity and extensibility. At the same time, I keep getting frustrated when I see such an elegant thing fade away gradually given that a) D has dropped out of top 20 in TIOBE Programming Community Index and b) it was not evaluated by the Computer Language Benchmarks Game any more. Most programmers know why this happens. I am simply frustrated.

D is falling while Go is rising. I do appreciate the philosophy behind the design of Go and trust Rob Pike and Ken Thompson to deliver another great product, but right now I do not see Go as a replacement of any mainstream programming languages as long as it is way slower than Java, not to speak C/C++. To me, Go’s rising is merely due to the support from Google. It is good as a research project, but it needs time to reach the critical mass in practice.

While reading the Computer Language Benchmarks Game, I am really amazed by LuaJIT. Probably I am going to try it some day."


Some of his posts on efficiency of data structures are worth reading, particularly on hash tables, btrees/redblack trees/sorting (might be old to you, but there was some new stuff for me):

https://attractivechaos.wordpress.com/tag/benchmark/

Speed and memory. The larger the hash table, the fewer collisions may occur and the faster the speed. For the same hash library, increasing memory always increases speed. When we compare two libraries, both speed and memory should be considered.

C vs. C++. All C++ implementations have similar API. It is also very easy to use for any type of keys. Both C libraries, ghthash and glib, can only keep pointers to the keys, which complicates API and increases memory especially for 64-bit systems where a pointer takes 8 bytes. In general, C++ libraries is perferred over C ones. Surprisingly, on 32-bit Mac OS X, glib outperforms TR1 and STL for string input. This might indicate that the glib implementation itself is very efficient, but just the lack of functionality in C affects the performance.
Generic programming in C. Except my khash.h, all the other C hash libraries use (void*) to achieve generic typing. Using void* is okey for strings, but will cause overhead for integers. This is why all C libraries, except khash.h, is slower than C++ libraries on integer keys, but close to on string keys.
Open addressing vs. chaining hash. Khash and google hash implement open addressing hash while the remaining implement chaining hash. In open addressing hash, the size of each bucket equals the size of a key plus 0.25 byte. Google sparsehash further compresses unused bucket to 1 bit, achieving high memory efficiency. In chaining hash, the memory overhead of each bucket is at least 4 bytes on 32bit machines, or 8 bytes on 64bit machines. However, chaining hash is less affected when the hash table is nearly full. In practice, both open addressing and chaining hash occupy similar memory under similar speed. Khash takes less peak memory mainly due to its advanced technique in rehashing which reduces memory usage. So far as speed is concerned, chaining hash may have fewer comparison between keys. We can see this from the fact that the speed of chaining hash approaches that of open addressing hash on string keys but much slower on integer keys.

Memory usage of search trees. B-tree is the winner here. Each element in the B-tree only needs one additional pointer. When there are enough elements, a B-tree is at least halfly full; on average it should be around 75% full. And so on 64-bit systems, for a B-tree with N elements, we need additional N*8/0.75=10N bytes memory. Splay tree will need N*8*2=16N extra space. RB tree is the worst.
Other issues. a) Google hash becomes unbearably slow when I try to put a lot of strings in the hash table. All the other libraries do not have this problem. b) Google hash performs more comparisons than khash. This is obvious because google-dense is clearly faster on integer keys but comparable to khash on string keys.

Concluding remarks

C++ hash library is much easier to use than C libraries. This is definitely where C++ is preferred over C.
TR1 hash implementation is no faster than STL implementation. They may outperform one another under certain input or settings.
SGI hash_map is faster and takes less memory than STL map. Unless ordering is important, hash_map is a better container than map.
Google hash is a worthy choice when we understand why it is slow for many string keys.
My khash library, which is a single-file C++ template header, achieves good balance between speed and memory. All my source codes are available at the Programs page.
Update

C interface can be elegant, too, if we implement it cleverly. See this post.
I realize that we just need one lookup to achieve “insert if absent; delete otherwise”. This further improves the speed for all C++ libraries.
I have analyzed google dense hash table in this post which explains why it is faster than khash on integer keys but close to or slower than on string keys.