On Wednesday, 10 June 2015 at 08:50:31 UTC, Dennis Ritchie wrote:
> On Wednesday, 10 June 2015 at 08:39:12 UTC, ixid wrote:
>> I suspect this is more about who the Mathematica and D users are as Project Euler is mostly mathematical rather than code optimization.
> 		
> Here and I say that despite the fact that in D BigInt not optimized very well, it helps me to solve a wide range of tasks that do not require high performance, so I want to BLAS or something similar was in D. Something is better than nothing!

You rarely need to use BigInt for heavy lifting though, often it's just summing, not that I would argue against optimization. I think speed is absolutely vital and one of the most powerful things we could do to promote D would be to run the best benchmarks site for all language comers and make sure D does very well. Every time there's a benchmark contest it seems to unearth D performance issues that can be greatly improved upon.

I'm sure you will beat me pretty quickly, as I said my maths isn't very good but it might motivate me to solve some more! =)

On Wednesday, 10 June 2015 at 09:12:17 UTC, John Chapman wrote:
> HMAC (for OAuth)

https://github.com/D-Programming-Language/phobos/pull/3233

Unfortunately it triggers a module cycle bug on FreeBSD that I can't figure out, so it hasn't been merged yet.

On 6/9/15 5:46 PM, Andrei Alexandrescu wrote:
> On 6/9/15 1:53 PM, Steven Schveighoffer wrote:
>> On 6/9/15 2:59 PM, Andrei Alexandrescu wrote:
>>> On 6/9/15 11:42 AM, Dennis Ritchie wrote:
>>>> "And finally `std.bigint` offers good (but not outstanding)
>>>> performance."
>>>
>>> BigInt should use reference counting. Its current approach to allocating
>>> new memory for everything is a liability. Could someone file a report
>>> for this please. -- Andrei
>>
>> Slightly OT, but this reminds me.
>>
>> RefCounted is not viable when using the GC, because any references on
>> the heap may race against stack-based references.
>
> How do you mean that?

If you add an instance of RefCounted to a GC-destructed type (either in an array, or as a member of a class), there is the potential that the GC will run the dtor of the RefCounted item in a different thread, opening up the possibility of races.

>> Can we make RefCounted use atomicInc and atomicDec? It will hurt
>> performance a bit, but the current state is not good.
>>
>> I spoke with Erik about this, as he was planning on using RefCounted,
>> but didn't know about the hairy issues with the GC.
>>
>> If we get to a point where we can have a thread-local GC, we can remove
>> the implementation detail of using atomic operations when possible.
>
> The obvious solution that comes to mind is adding a Flag!"interlocked".

Can you explain it further? It's not obvious to me.

-Steve

On 6/10/15 1:53 AM, ponce wrote:
> On Wednesday, 10 June 2015 at 07:56:46 UTC, John Chapman wrote:
>> It's a shame ucent/cent never got implemented. But couldn't they be
>> added to Phobos? I often need a 128-bit type with better precision
>> than float and double.
>
> FWIW:
> https://github.com/d-gamedev-team/gfm/blob/master/math/gfm/math/wideint.d

Yes, arbitrary fixed-size integrals would be good to have in Phobos. Who's the author of that code? Can we get something going here? -- Andrei

On 6/10/15 3:52 AM, Steven Schveighoffer wrote:
> On 6/9/15 5:46 PM, Andrei Alexandrescu wrote:
>> On 6/9/15 1:53 PM, Steven Schveighoffer wrote:
>>> On 6/9/15 2:59 PM, Andrei Alexandrescu wrote:
>>>> On 6/9/15 11:42 AM, Dennis Ritchie wrote:
>>>>> "And finally `std.bigint` offers good (but not outstanding)
>>>>> performance."
>>>>
>>>> BigInt should use reference counting. Its current approach to
>>>> allocating
>>>> new memory for everything is a liability. Could someone file a report
>>>> for this please. -- Andrei
>>>
>>> Slightly OT, but this reminds me.
>>>
>>> RefCounted is not viable when using the GC, because any references on
>>> the heap may race against stack-based references.
>>
>> How do you mean that?
>
> If you add an instance of RefCounted to a GC-destructed type (either in
> an array, or as a member of a class), there is the potential that the GC
> will run the dtor of the RefCounted item in a different thread, opening
> up the possibility of races.

That's a problem with the GC. Collected memory must be deallocated in the thread that allocated it. It's not really that complicated to implement, either - the collection process puts the memory to deallocate in a per-thread freelist; then when each thread wakes up and tries to allocate things, it first allocates from the freelist.

>>> Can we make RefCounted use atomicInc and atomicDec? It will hurt
>>> performance a bit, but the current state is not good.
>>>
>>> I spoke with Erik about this, as he was planning on using RefCounted,
>>> but didn't know about the hairy issues with the GC.
>>>
>>> If we get to a point where we can have a thread-local GC, we can remove
>>> the implementation detail of using atomic operations when possible.
>>
>> The obvious solution that comes to mind is adding a Flag!"interlocked".
>
> Can you explain it further? It's not obvious to me.

The RefCounted type could have a flag as a template parameter.


Andrei

On 6/10/15 11:49 AM, Andrei Alexandrescu wrote:
> On 6/10/15 3:52 AM, Steven Schveighoffer wrote:
>> On 6/9/15 5:46 PM, Andrei Alexandrescu wrote:
>>> On 6/9/15 1:53 PM, Steven Schveighoffer wrote:
>>>> On 6/9/15 2:59 PM, Andrei Alexandrescu wrote:
>>>>> On 6/9/15 11:42 AM, Dennis Ritchie wrote:
>>>>>> "And finally `std.bigint` offers good (but not outstanding)
>>>>>> performance."
>>>>>
>>>>> BigInt should use reference counting. Its current approach to
>>>>> allocating
>>>>> new memory for everything is a liability. Could someone file a report
>>>>> for this please. -- Andrei
>>>>
>>>> Slightly OT, but this reminds me.
>>>>
>>>> RefCounted is not viable when using the GC, because any references on
>>>> the heap may race against stack-based references.
>>>
>>> How do you mean that?
>>
>> If you add an instance of RefCounted to a GC-destructed type (either in
>> an array, or as a member of a class), there is the potential that the GC
>> will run the dtor of the RefCounted item in a different thread, opening
>> up the possibility of races.
>
> That's a problem with the GC. Collected memory must be deallocated in
> the thread that allocated it. It's not really that complicated to
> implement, either - the collection process puts the memory to deallocate
> in a per-thread freelist; then when each thread wakes up and tries to
> allocate things, it first allocates from the freelist.

I agree it's a problem with the GC, but not that it's a simple fix. It's not just a freelist -- the dtor needs to be run in the thread also. But the amount of affected code (i.e. any code that uses GC) makes this a very high risk change, whereas changing RefCounted is a 2-line change that is easy to prove/review. I will make the RefCounted atomic PR if you can accept that.

>>>> Can we make RefCounted use atomicInc and atomicDec? It will hurt
>>>> performance a bit, but the current state is not good.
>>>>
>>>> I spoke with Erik about this, as he was planning on using RefCounted,
>>>> but didn't know about the hairy issues with the GC.
>>>>
>>>> If we get to a point where we can have a thread-local GC, we can remove
>>>> the implementation detail of using atomic operations when possible.
>>>
>>> The obvious solution that comes to mind is adding a Flag!"interlocked".
>>
>> Can you explain it further? It's not obvious to me.
>
> The RefCounted type could have a flag as a template parameter.

OK, thanks for the explanation. I'd do it the other way around: Flag!"threadlocal", since we should be safe by default.

-Steve

On Wednesday, 10 June 2015 at 09:43:47 UTC, ixid wrote:
> You rarely need to use BigInt for heavy lifting though, often it's just summing, not that I would argue against optimization. I think speed is absolutely vital and one of the most powerful things we could do to promote D would be to run the best benchmarks site for all language comers and make sure D does very well. Every time there's a benchmark contest it seems to unearth D performance issues that can be greatly improved upon.

Yes it is. Many are trying to find performance problems D. And sometimes it turns out.

> I'm sure you will beat me pretty quickly, as I said my maths isn't very good but it might motivate me to solve some more! =)

No, I will start to beat you until next year, because, unfortunately, I will not have a full year of access to the computer. We can say that this is something like a long vacation :)

On Wednesday, 10 June 2015 at 20:31:52 UTC, Steven Schveighoffer wrote:
> OK, thanks for the explanation. I'd do it the other way around: Flag!"threadlocal", since we should be safe by default.

`RefCounted!T` is also thread-local by default, only `shared(RefCounted!T)` needs to use atomic operations.

On 6/11/15 4:15 AM, "Marc =?UTF-8?B?U2Now7x0eiI=?= <schuetzm@gmx.net>" wrote:
> On Wednesday, 10 June 2015 at 20:31:52 UTC, Steven Schveighoffer wrote:
>> OK, thanks for the explanation. I'd do it the other way around:
>> Flag!"threadlocal", since we should be safe by default.
>
> `RefCounted!T` is also thread-local by default, only
> `shared(RefCounted!T)` needs to use atomic operations.

I may have misunderstood Andrei. We can't just use a flag to fix this problem, all allocations are in danger of races (even thread-local ones). But maybe he meant *after* we fix the GC we could add a flag? I'm not sure.

A flag at this point would be a band-aid fix, allowing one to optimize if one knows that his code never puts RefCounted instances on the heap. Hard to prove...

-Steve

On 6/11/15 5:17 AM, Steven Schveighoffer wrote:
> On 6/11/15 4:15 AM, "Marc =?UTF-8?B?U2Now7x0eiI=?= <schuetzm@gmx.net>"
> wrote:
>> On Wednesday, 10 June 2015 at 20:31:52 UTC, Steven Schveighoffer wrote:
>>> OK, thanks for the explanation. I'd do it the other way around:
>>> Flag!"threadlocal", since we should be safe by default.
>>
>> `RefCounted!T` is also thread-local by default, only
>> `shared(RefCounted!T)` needs to use atomic operations.
>
> I may have misunderstood Andrei. We can't just use a flag to fix this
> problem, all allocations are in danger of races (even thread-local
> ones). But maybe he meant *after* we fix the GC we could add a flag? I'm
> not sure.

Yes, we definitely need to fix the GC. -- Andrei