subject:"Challenge"

Re: Challenge Tuples

2024-05-03 Thread NotYouAgain via Digitalmars-d-learn


On Friday, 3 May 2024 at 05:11:28 UTC, Salih Dincer wrote:


..
Wouldn't it be great if there was a feature that worked at 
runtime...


SDB@79


module m;
@safe:
private:
import std;

void main()
{
auto myTuple = tuple(1, 2, 3, [1, 3], 5);
int[] arrToSum;

foreach(int i, val; myTuple.expand)
{
if(typeof(val).stringof == "int[]")
{
foreach(v; myTuple.expand[i..i+1])
arrToSum ~= v;
}
else
{
arrToSum ~= val;
}
}

writefln("The total value of the tuples is: %s", 
arrToSum.sum); // 15

}

Re: Challenge Tuples

2024-05-02 Thread Salih Dincer via Digitalmars-d-learn


On Wednesday, 1 May 2024 at 14:15:19 UTC, Andrey Zherikov wrote:



Shorter and without allocations:
```d
import std.typecons : tuple;
import std.algorithm : sum, each;

auto sum(int i) => i;

void main()
{
  auto t = tuple(1, 2, 3, [1, 3], 5);

  int res=0;
  t.each!(e => res += sum(e));
  assert(res == 15);
}
```


Super!

In summary, D is clearly ahead of the tuple. Especially with its 
features similar to AliasSeq, I think it is unrivaled. Wouldn't 
it be great if there was a feature that worked at runtime...


SDB@79

Re: Challenge Tuples

2024-05-01 Thread Andrey Zherikov via Digitalmars-d-learn


On Friday, 26 April 2024 at 13:25:34 UTC, Salih Dincer wrote:
You have a 5-item data tuples as Tuple(1, 2, 3, [1, 3], 5) and 
implement the sum (total = 15) with the least codes using the 
sum() function of the language you are coding...



Let's start with D:

```d
import std.typecons : tuple;
import std.algorithm : sum;

void main()
{
  auto t = tuple(1, 2, 3, [1, 3], 5);

  int[] arr;
  t.each!(e => arr ~= e);
  assert(arr.sum == 15);
}
```

and bonus:

```d
import std.typecons : tuple;
import std.stdio : writeln;
void main()
{
  auto t = tuple(1, 2, 3, [1, 3], 5);
  auto results = [0];

  foreach (data; t)
  {
static
if (is(typeof(data) == int[]))
{
  int sum;
  foreach (d; data)
  {
sum += d;
  }
  results ~= sum;
}
else
{
  results ~= data;
}
  }
  results.writeln; // [0, 1, 2, 3, 4, 5]
```

I bet you won't be able to do it this easily with other 
languages!  Note: I tried with C# and Python and it didn't work!


SDB@79



Shorter and without allocations:
```d
import std.typecons : tuple;
import std.algorithm : sum, each;

auto sum(int i) => i;

void main()
{
  auto t = tuple(1, 2, 3, [1, 3], 5);

  int res=0;
  t.each!(e => res += sum(e));
  assert(res == 15);
}
```

Re: Challenge Tuples

2024-04-27 Thread Julian Fondren via Digitalmars-d-learn


On Friday, 26 April 2024 at 13:25:34 UTC, Salih Dincer wrote:
You have a 5-item data tuples as Tuple(1, 2, 3, [1, 3], 5) and 
implement the sum (total = 15) with the least codes using the 
sum() function of the language you are coding...


Nim:

```nim
import std/[math, typetraits, macros]

macro unrollRange(low, high: static int; name, body: untyped) =
  result = newStmtList()
  for i in low ..< high:
result.add(newBlockStmt(newStmtList(
  newConstStmt(name, newLit i),
  copy body
)))

let t = (1, 2, 3, @[1, 3], 5)
var arr: seq[int]
unrollRange(0, t.tupleLen, i):
  arr.add t[i]
doAssert arr.sum == 15
```

vs. D

1. there's no `each` on tuples
2. there's no static for loop, so a macro is needed for the tuple 
indices

3. `add` is making use of the same overload as D's `~=`

Re: Challenge Tuples

2024-04-27 Thread Sergey via Digitalmars-d-learn


On Friday, 26 April 2024 at 13:25:34 UTC, Salih Dincer wrote:
You have a 5-item data tuples as Tuple(1, 2, 3, [1, 3], 5) and 
implement the sum (total = 15) with the least codes using the 
sum() function of the language you are coding...



Let's start with D:

```d
import std.typecons : tuple;
import std.algorithm : sum;

void main()
{
  auto t = tuple(1, 2, 3, [1, 3], 5);

  int[] arr;
  t.each!(e => arr ~= e);
  assert(arr.sum == 15);
}
```
I bet you won't be able to do it this easily with other 
languages!  Note: I tried with C# and Python and it didn't work!


For Python it is possible to use something like:
```python
t = (1,2,3,[1,3],5)
for e in t:
a.append(e) if isinstance(e, int) else a.extend(e)
print(sum(a))
```

Re: Challenge Tuples

2024-04-27 Thread Salih Dincer via Digitalmars-d-learn


On Saturday, 27 April 2024 at 15:36:40 UTC, Nick Treleaven wrote:
On Saturday, 27 April 2024 at 15:32:40 UTC, Nick Treleaven 
wrote:

On Saturday, 27 April 2024 at 11:55:58 UTC, Basile B. wrote:

foreach const e in u do
if echo(is, e, T) do
result += e;



static if (is(typeof(e) == int))
r += e;


Actually I would write that:
```d
R r;
foreach (e; v)
{
static if (is(typeof(e) : R))
```


I like the new sum() function, great Nick!  Moreover, it also 
works with an ordinary range:


```d
  enum limit = 100; // sum = 5050
  iota(limit + 1).sum.writeln;
```

Python seems too complicated to me, but C# looks delicious. 
Moreover, it was implemented without defining IEnumerator. Well 
done Matheus!


SDB@79

Re: Challenge Tuples

2024-04-27 Thread Nick Treleaven via Digitalmars-d-learn


On Saturday, 27 April 2024 at 15:32:40 UTC, Nick Treleaven wrote:

On Saturday, 27 April 2024 at 11:55:58 UTC, Basile B. wrote:

foreach const e in u do
if echo(is, e, T) do
result += e;



static if (is(typeof(e) == int))
r += e;


Actually I would write that:
```d
R r;
foreach (e; v)
{
static if (is(typeof(e) : R))
```

Re: Challenge Tuples

2024-04-27 Thread Nick Treleaven via Digitalmars-d-learn


On Saturday, 27 April 2024 at 11:55:58 UTC, Basile B. wrote:

Here's [STYX](https://gitlab.com/styx-lang/styx) solution:


function sum[T,U](U u): u32


I think you meant `: T`.


{
var T result;
foreach const e in u do
if echo(is, e, T) do
result += e;
else do
result += sum![T](e);
return result;
}

function main(): s32
{
assert((1, 2, 3, [1, 3], 5).sum![u32]() == 15);
return 0;
}


Mostly equivalent D:
```d
R sum(R = long, T)(T v)
{
R r;
foreach (e; v)
{
static if (is(typeof(e) == int))
r += e;
else
r += sum!R(e);
}
return r;
}

void main()
{
import std;
assert(tuple(1, 2, 3, [1, 3], 5).sum == 15);
}
```

Re: Challenge Tuples

2024-04-27 Thread Basile B. via Digitalmars-d-learn


On Friday, 26 April 2024 at 13:25:34 UTC, Salih Dincer wrote:
You have a 5-item data tuples as Tuple(1, 2, 3, [1, 3], 5) and 
implement the sum (total = 15) with the least codes using the 
sum() function of the language you are coding...



Let's start with D:


Here's [STYX](https://gitlab.com/styx-lang/styx) solution:


function sum[T,U](U u): u32
{
var T result;
foreach const e in u do
if echo(is, e, T) do
result += e;
else do
result += sum![T](e);
return result;
}

function main(): s32
{
assert((1, 2, 3, [1, 3], 5).sum![u32]() == 15);
return 0;
}


A few notes:

- tuples are first class citizen
- `foreach` over tuple is like in D, i.e unrolling
- `echo` is like D `__traits`
- _Implicit Generic Application_ of `U` (that's like D's IFTI) 
makes the task easy

Re: Challenge Tuples

2024-04-26 Thread Andy Valencia via Digitalmars-d-learn


On Friday, 26 April 2024 at 13:25:34 UTC, Salih Dincer wrote:
You have a 5-item data tuples as Tuple(1, 2, 3, [1, 3], 5) and 
implement the sum (total = 15) with the least codes using the 
sum() function of the language you are coding...


My Python solution (function named dosum to avoid collision w. 
Python primitive):


def dosum(itm):
if isinstance(itm, (int, float)):
return itm
return sum( dosum(_i) for _i in itm );

print dosum( [1, 2, 3, [1, 3], 5] )

Re: Challenge Tuples

2024-04-26 Thread matheus via Digitalmars-d-learn


On Friday, 26 April 2024 at 13:25:34 UTC, Salih Dincer wrote:

...


Very nice, for your first example I need to think a bit because 
I'm bit rusty in C#, but I think it will not be as easier as D 
version.


For the bonus part:

private static void Main(string[] args){
var a = (1,2,3,(1,3),5);
var t = a as ITuple;
var xx = new List();

for(var i=0;i   if(t[i].GetType() == 
typeof(System.ValueTuple)){

  var t2 = (t[i] as ITuple);
  var s = 0;
  for(var j=0;jAgain I'm rusty in C#... but so far yes it's more verbose than 
the D version.


Matheus.

Challenge Tuples

2024-04-26 Thread Salih Dincer via Digitalmars-d-learn

You have a 5-item data tuples as Tuple(1, 2, 3, [1, 3], 5) and 
implement the sum (total = 15) with the least codes using the 
sum() function of the language you are coding...



Let's start with D:

```d
import std.typecons : tuple;
import std.algorithm : sum;

void main()
{
  auto t = tuple(1, 2, 3, [1, 3], 5);

  int[] arr;
  t.each!(e => arr ~= e);
  assert(arr.sum == 15);
}
```

and bonus:

```d
import std.typecons : tuple;
import std.stdio : writeln;
void main()
{
  auto t = tuple(1, 2, 3, [1, 3], 5);
  auto results = [0];

  foreach (data; t)
  {
static
if (is(typeof(data) == int[]))
{
  int sum;
  foreach (d; data)
  {
sum += d;
  }
  results ~= sum;
}
else
{
  results ~= data;
}
  }
  results.writeln; // [0, 1, 2, 3, 4, 5]
```

I bet you won't be able to do it this easily with other 
languages!  Note: I tried with C# and Python and it didn't work!


SDB@79

Re: Challenge: Make a data type for holding one of 8 directions allowing increment and overflow

2024-03-16 Thread Richard (Rikki) Andrew Cattermole via Digitalmars-d-learn

Bit fields are currently going through the DIP process, although because 
of ImportC having it, its just a matter of turning them on and adding 
the parser stuff.


However there is a major drawback to it and is why you'll still need to 
use a struct and that is you can't take a pointer to it.

Re: Challenge: Make a data type for holding one of 8 directions allowing increment and overflow

2024-03-16 Thread H. S. Teoh via Digitalmars-d-learn

On Sat, Mar 16, 2024 at 09:16:51PM +, Liam McGillivray via 
Digitalmars-d-learn wrote:
> On Friday, 15 March 2024 at 00:21:42 UTC, H. S. Teoh wrote:
[...]
> > When dealing with units of data smaller than a byte, you generally
> > need to do it manually, because memory is not addressable by
> > individual bits, making it difficult to implement things like
> > slicing an array of bool.
[...]
> I'm curious as to what "manual implementation" would mean, since
> clearly making my own struct with `bool[3]` doesn't count. Does D have
> features for precise memory manipulation?

Manual implementation as in you would deal with the machine
representation in terms of bytes, or more likely, uints (on modern CPUs
even though bytes are individually addressible, the hardware actually
works in terms of a larger unit, typically an 4-byte 32-bit unit, or an
8-byte 64-bit unit), using bitwise operators to manipulate the bits the
way you want to.

> Anyway, I'm surprised that D has a special operator `&=` for doing bit
> manipulation on integers, especially given that the steps to convert
> an int into a bool array is more complicated. I would imagine the
> former would be a rather niche thing.

You should understand that bitwise operators are directly implemented in
hardware, and thus operators like &, |, ^, <<, >>, ~, etc., typically
map directly to individual CPU instructions. As such, they are very
fast, and preferred when you're doing bit-level manipulations.  At this
level, you typically do not work with individual bits per se, but with
machine words (typically 32-bit or 64-bit units).  Bitwise operators
operate on all 32 or 64 bits at once, so performance-aware code
typically manipulates all these bits simultaneously rather than
individually.  Of course, using suitable bit-masking you *can* address
individual bits, but the hardware instructions themselves typically work
with all 32/64 bits at once.

Here's a simple example. Suppose you have 3 bits you want to store.
Since the machine doesn't have a 3-bit built-in type, you typically just
use the next larger available size, either a ubyte (8 bits) if you want
compact storage, or if compactness isn't a big issue just a uint (32
bits, you just ignore the other 29 bits that you don't need). So you'd
declare the storage something like this:

uint myBits;

Bits are usually indexed from 0, so bit 0 is the first position, bit 1
is the second position, and so on.  So to set the first bit to 1, you'd
do:

myBits |= 0b001;

Note that at the machine level, this operator works on all 32 bits at
the same time. Most of the bits remain unchanged, though, because
bitwise OR does not change the original value if the operand is 0. So
the overall effect is that the first bit is set.

To set the first bit to 0, there isn't a direct operator that does that,
but you can take advantage of the behaviour of bitwise AND, in which
any bit which is 0 in the operand will get cleared, everything else
remains unchanged. So you'd do this:

myBits &= 0b110;

Now, since we don't really care about the other 29 bits, we could write
this as follows instead, to make our intent clearer:

myBits &= ~0b001;

The ~ operator flips all the bits, so this is equivalent to writing:

myBits &= ~0b_______1110;

Writing it with ~ also has the advantage that should we later decide to
add another bit to our "bit array", we don't have to update the code;
whereas if we'd used `myBits &= 0b110;` then we'd need to change it to
`myBits &= 0b1110;` otherwise our new 4th bit may get unexpectedly
cleared when we only wanted to clear the first bit.

Now, what if we wanted to set both the 1st and 3rd bits?  In a
hypothetical bit array implementation, we'd do the equivalent of:

bool[3] myBits;
myBits[0] = 1;
myBits[2] = 1;

However, in our uint approach, we can cut the number of operations by
half, because the CPU is already operating on the entire 32 bits of the
uint at once -- so there's no need to have two instructions to set two
individual bits when we could just do it all in one:

myBits |= 0b101; // look, ma! both bits set at once!

Similarly, to clear the 1st and 3rd bits simultaneously, we simply
write:

myBits &= ~0b101; // clear both bits in 1 instruction!

Of course, when we only have 3 bits to work with, the savings isn't that
significant.  However, if you have a larger bit array, say you need an
array of 32 bits, this can speed your code up by 32x, because you're
taking advantage of the fact that the hardware is already operating on
all 32 bits at the same time.  On 64-bit CPUs, you can speed it up by
64x because the CPU operates on all 64 bits simultaneously, so you can
manipulate an entire array of 64 bits in a single instruction, which is
64x faster than if you looped over an array of bool with 64 iterations.

T

-- 
Without outlines, life would be pointless.

Re: Challenge: Make a data type for holding one of 8 directions allowing increment and overflow

2024-03-16 Thread Liam McGillivray via Digitalmars-d-learn


On Friday, 15 March 2024 at 17:25:09 UTC, Daniel N wrote:
On Tuesday, 12 March 2024 at 05:38:03 UTC, Liam McGillivray 
wrote:
I am in need of a data type for holding direction information; 
one of 8 directions on a single axis. They are named in terms 
of compass directions. If D had a 4-bit datatype, I would just 
use this and do `+=2` whenever I want to change the datatype, 
but it doesn't.


Perhaps this would be a good programming challenge for someone 
more experienced than me. Make a data type (probably a struct) 
for holding one of 8 directional values using 3 bits. It 
should accept the use of increment operators to change the 
angle.


Ideally (but optionally), it should work as an enum of the 
same name; "Direction".


Here's a unittest that it should ideally pass:


D actually supports both 3 and 4 bit integers. People will 
likely warn you of minor portability risks... but if you target 
a limited amount of platforms and prefer concise readable code, 
then it's a text book example for bitfields. The risk can 
easily be mitigated by having an unittest to catch the error 
directly(if you try to port to some exotic platform).


dmd -preview=bitfields

(Some lines stolen from Rikki)

```d
struct Direction
{
private uint value : 3;
alias this = value;

enum Direction N  = Direction(0);
enum Direction NE = Direction(1);
enum Direction E  = Direction(2);
enum Direction SE = Direction(3);
enum Direction S  = Direction(4);
enum Direction SW = Direction(5);
enum Direction W  = Direction(6);
enum Direction NW = Direction(7);
}
```


Oh wow! That looks so clean and elegant, aside from the `: 3` 
part being easy to miss, and not very readable for those not 
aware of this feature. This would be so simple. If I used this, I 
wouldn't even need to make a struct and write the operator 
overload functions; just make an enum for a 3-bit uint.


Based on the words in the command and a quick search, I'm 
guessing that this is an experimental feature that has not yet 
been accepted as part of the language. Perhaps I shouldn't use 
this then, just in case it gets pulled and someone who discovers 
my project in the future will have a build error that they don't 
know how to solve. This seems like a bigger problem than the 
extra memory the current ubyte version takes up, which is 
probably quite small for a computer of today anyway.


I suppose this would be a nice feature for the language to have 
if the syntax were reworked. Perhaps something like `uint!3 
value;` would be better.

Re: Challenge: Make a data type for holding one of 8 directions allowing increment and overflow

2024-03-16 Thread Liam McGillivray via Digitalmars-d-learn


On Friday, 15 March 2024 at 00:21:42 UTC, H. S. Teoh wrote:
On Thu, Mar 14, 2024 at 11:39:33PM +, Liam McGillivray via 
Digitalmars-d-learn wrote: [...]
I tried to rework the functions to use bitwise operations, but 
it was difficult to figure out the correct logic. I decided 
that it's not worth the hassle, so I just changed the value 
storage from `bool[3]` to `ubyte`.

[...]

Just wanted to note that while in theory bool[3] could be 
optimized by the compiler for compact storage, what you're most 
likely to get is 3 bytes, one for each bool, or perhaps even 3 
ints (24 bytes). When dealing with units of data smaller than a 
byte, you generally need to do it manually, because memory is 
not addressable by individual bits, making it difficult to 
implement things like slicing an array of bool. So the compiler 
is most likely to simplify things by making it an array of 
bytes rather than emit complex bit manipulation code to make up 
for the lack of bit-addressability in the underlying hardware.


Using bit operators like others have pointed out in this thread 
is probably the best way to implement what you want.


T


I'm curious as to what "manual implementation" would mean, since 
clearly making my own struct with `bool[3]` doesn't count. Does D 
have features for precise memory manipulation?


Anyway, I'm surprised that D has a special operator `&=` for 
doing bit manipulation on integers, especially given that the 
steps to convert an int into a bool array is more complicated. I 
would imagine the former would be a rather niche thing.

Re: Challenge: Make a data type for holding one of 8 directions allowing increment and overflow

2024-03-15 Thread Daniel N via Digitalmars-d-learn


On Tuesday, 12 March 2024 at 05:38:03 UTC, Liam McGillivray wrote:
I am in need of a data type for holding direction information; 
one of 8 directions on a single axis. They are named in terms 
of compass directions. If D had a 4-bit datatype, I would just 
use this and do `+=2` whenever I want to change the datatype, 
but it doesn't.


Perhaps this would be a good programming challenge for someone 
more experienced than me. Make a data type (probably a struct) 
for holding one of 8 directional values using 3 bits. It should 
accept the use of increment operators to change the angle.


Ideally (but optionally), it should work as an enum of the same 
name; "Direction".


Here's a unittest that it should ideally pass:


D actually supports both 3 and 4 bit integers. People will likely 
warn you of minor portability risks... but if you target a 
limited amount of platforms and prefer concise readable code, 
then it's a text book example for bitfields. The risk can easily 
be mitigated by having an unittest to catch the error directly(if 
you try to port to some exotic platform).


dmd -preview=bitfields

(Some lines stolen from Rikki)

```d
struct Direction
{
private uint value : 3;
alias this = value;

enum Direction N  = Direction(0);
enum Direction NE = Direction(1);
enum Direction E  = Direction(2);
enum Direction SE = Direction(3);
enum Direction S  = Direction(4);
enum Direction SW = Direction(5);
enum Direction W  = Direction(6);
enum Direction NW = Direction(7);
}
```

Re: Challenge: Make a data type for holding one of 8 directions allowing increment and overflow

2024-03-14 Thread H. S. Teoh via Digitalmars-d-learn

On Thu, Mar 14, 2024 at 11:39:33PM +, Liam McGillivray via 
Digitalmars-d-learn wrote:
[...]
> I tried to rework the functions to use bitwise operations, but it was
> difficult to figure out the correct logic. I decided that it's not
> worth the hassle, so I just changed the value storage from `bool[3]`
> to `ubyte`.
[...]

Just wanted to note that while in theory bool[3] could be optimized by
the compiler for compact storage, what you're most likely to get is 3
bytes, one for each bool, or perhaps even 3 ints (24 bytes). When
dealing with units of data smaller than a byte, you generally need to do
it manually, because memory is not addressable by individual bits,
making it difficult to implement things like slicing an array of bool.
So the compiler is most likely to simplify things by making it an array
of bytes rather than emit complex bit manipulation code to make up for
the lack of bit-addressability in the underlying hardware.

Using bit operators like others have pointed out in this thread is
probably the best way to implement what you want.

T

-- 
LINUX = Lousy Interface for Nefarious Unix Xenophobes.

Re: Challenge: Make a data type for holding one of 8 directions allowing increment and overflow

2024-03-14 Thread Basile B. via Digitalmars-d-learn

On Friday, 15 March 2024 at 00:00:01 UTC, Richard (Rikki) Andrew
Cattermole wrote:

On 15/03/2024 12:47 PM, Basile B. wrote:
On Thursday, 14 March 2024 at 23:39:33 UTC, Liam McGillivray
wrote:
On Thursday, 14 March 2024 at 01:58:46 UTC, Richard (Rikki)
Andrew Cattermole wrote:

[...]

I tried to rework the functions to use bitwise operations,
but it was difficult to figure out the correct logic. I
decided that it's not worth the hassle, so I just changed the
value storage from `bool[3]` to `ubyte`. Now it works much
more like your version.

https://github.com/LiamM32/Open_Emblem/blob/c2014ab3f77e89c0cedcd6dbf7f8362ebfac33a9/source/common.d

I did a little reading, so now I understand what it means
when you have `&= 7`. But I want to ask, is this faster than
`%= 8`? If not, I would like to change it to the latter for
readability.

`%=8` will be codegened using slower intructions w/o optimz
enabled but with `&=7` you directly get the right instruction,
which does not involves integer division. See
https://godbolt.org/z/74vbba5aG

Yes, it'll depend upon how smart the compiler is at optimizing
and it may not occur in non-optimizing builds.

Indeed GDC (so very likely GCC too, or whatever language uses it
as backend...) does it without optimz
(https://godbolt.org/z/Ke7c54Gqj).

That's not very surprising. If you look at LLVM bug tracker, for
the tag "missed optimisations", in the report body you'll see a
lot of "GDC does that but we dont", even if here it's a bit
different, as optimz are not enabled.

Re: Challenge: Make a data type for holding one of 8 directions allowing increment and overflow

2024-03-14 Thread Richard (Rikki) Andrew Cattermole via Digitalmars-d-learn




On 15/03/2024 12:47 PM, Basile B. wrote:

On Thursday, 14 March 2024 at 23:39:33 UTC, Liam McGillivray wrote:
On Thursday, 14 March 2024 at 01:58:46 UTC, Richard (Rikki) Andrew 
Cattermole wrote:

[...]


I tried to rework the functions to use bitwise operations, but it was 
difficult to figure out the correct logic. I decided that it's not 
worth the hassle, so I just changed the value storage from `bool[3]` 
to `ubyte`. Now it works much more like your version.

https://github.com/LiamM32/Open_Emblem/blob/c2014ab3f77e89c0cedcd6dbf7f8362ebfac33a9/source/common.d

I did a little reading, so now I understand what it means when you 
have `&= 7`. But I want to ask, is this faster than `%= 8`? If not, I 
would like to change it to the latter for readability.


`%=8` will be codegened using slower intructions w/o optimz enabled but 
with `&=7` you directly get the right instruction, which does not 
involves integer division. See https://godbolt.org/z/74vbba5aG


Yes, it'll depend upon how smart the compiler is at optimizing and it 
may not occur in non-optimizing builds.


The modulas instructions are based upon division, this is an incredibly 
expensive operation.


https://stackoverflow.com/a/8022107

The division instruction on Haswell for integers ranges from 9 cycles 
for 8bit, all the way up to 36 cycles for 64bit.

Re: Challenge: Make a data type for holding one of 8 directions allowing increment and overflow

2024-03-14 Thread Basile B. via Digitalmars-d-learn

On Thursday, 14 March 2024 at 23:39:33 UTC, Liam McGillivray 
wrote:
On Thursday, 14 March 2024 at 01:58:46 UTC, Richard (Rikki) 
Andrew Cattermole wrote:

[...]


I tried to rework the functions to use bitwise operations, but 
it was difficult to figure out the correct logic. I decided 
that it's not worth the hassle, so I just changed the value 
storage from `bool[3]` to `ubyte`. Now it works much more like 
your version.

https://github.com/LiamM32/Open_Emblem/blob/c2014ab3f77e89c0cedcd6dbf7f8362ebfac33a9/source/common.d

I did a little reading, so now I understand what it means when 
you have `&= 7`. But I want to ask, is this faster than `%= 8`? 
If not, I would like to change it to the latter for readability.


`%=8` will be codegened using slower intructions w/o optimz 
enabled but with `&=7` you directly get the right instruction, 
which does not involves integer division. See 
https://godbolt.org/z/74vbba5aG

Re: Challenge: Make a data type for holding one of 8 directions allowing increment and overflow

2024-03-14 Thread Liam McGillivray via Digitalmars-d-learn

On Thursday, 14 March 2024 at 01:58:46 UTC, Richard (Rikki) 
Andrew Cattermole wrote:
The cost of an add + increment then a bitwise and is only 2-4 
cycles on a Haswell cpu. Depending upon if its working solely 
in registers (via inlining) or its operating on ram.


Whereas if you need to do branching (if statement, loops), this 
is an unpredictable cost and loops where a simple bitwise 
operation can be done is out right non-optimized.


As for exceptions, totally not required. You can solve this by 
simply making your state private so nobody else can mutate it. 
Bounds checking will ensure if the state is corrupted it'll 
error out if you use the lookup method I suggested above.


I tried to rework the functions to use bitwise operations, but it 
was difficult to figure out the correct logic. I decided that 
it's not worth the hassle, so I just changed the value storage 
from `bool[3]` to `ubyte`. Now it works much more like your 
version.

https://github.com/LiamM32/Open_Emblem/blob/c2014ab3f77e89c0cedcd6dbf7f8362ebfac33a9/source/common.d

I did a little reading, so now I understand what it means when 
you have `&= 7`. But I want to ask, is this faster than `%= 8`? 
If not, I would like to change it to the latter for readability.

Re: Challenge: Make a data type for holding one of 8 directions allowing increment and overflow

2024-03-13 Thread Richard (Rikki) Andrew Cattermole via Digitalmars-d-learn

There appears to be a few things that you may not be aware of based upon 
this implementation.


The cost of an add + increment then a bitwise and is only 2-4 cycles on 
a Haswell cpu. Depending upon if its working solely in registers (via 
inlining) or its operating on ram.


The cost of a move from ram into a register is about 1 cycle, but can 
have latencies around 3 cycles if not cached.


Whereas if you need to do branching (if statement, loops), this is an 
unpredictable cost and loops where a simple bitwise operation can be 
done is out right non-optimized.


As for methods like to:

```d
static immutable string[] table = ["north", ...];
return table[this.value];
```

That's two moves from ram to register.

In essence in your design, you have blown out the cost by a significant 
margin well beyond the 12% that is described as being the minimum to 
consider optimization.


If you want to understand where the 12% number comes from I suggest 
reading the paper "Structured Programming with go to Statements" by 
Donald Knuth.


As for exceptions, totally not required. You can solve this by simply 
making your state private so nobody else can mutate it. Bounds checking 
will ensure if the state is corrupted it'll error out if you use the 
lookup method I suggested above.


Understanding what I have said is very important for game engine 
programmers. So if you're interested in it beyond some hobbyist 
endeavors you have some reading up to do ;)

Re: Challenge: Make a data type for holding one of 8 directions allowing increment and overflow

2024-03-13 Thread Liam McGillivray via Digitalmars-d-learn

On Tuesday, 12 March 2024 at 06:38:28 UTC, Richard (Rikki) Andrew 
Cattermole wrote:
By taking advantage of integer wrapping and a bitwise and, its 
quite a simple problem to solve!


Challenge for the reader: add support for binary operations and 
toString support.


Last night I pushed the latest commit to the GitHub repository 
for my game. It contains the `Direction` struct in 
[`source/common.d`](https://github.com/LiamM32/Open_Emblem/blob/master/source/common.d). Here it is:


```
struct Direction //One of 8 directions stored in 3 bits
{
import std.conv;
import std.traits: isNumeric;

bool[3] b;

static Direction N = Direction(b:[false,false,false]);
static Direction NE = Direction(b:[true,false,false]);
static Direction E = Direction(b:[false,true,false]);
static Direction SE = Direction(b:[true,true,false]);
static Direction S = Direction(b:[false,false,true]);
static Direction SW = Direction(b:[true,false,true]);
static Direction W = Direction(b:[false,true,true]);
static Direction NW = Direction(b:[true,true,true]);

ref Direction opUnary(string op)() if (op == "++" || op == 
"--") {

static if (op == "++") const bool up = true;
else const bool up = false;

if (b[0]) {
if (b[1]) b[2] = !b[2];
b[1] = !b[1];
}
b[0] = !b[0];
return this;
}

void opOpAssign(string op)(int amount) if (op == "+" || op == 
"-") {

amount = amount%8;
if (amount > 0) for (uint i = 0; i < amount; i++) {
static if (op=="+") this++;
else this--;
} else for (uint i=0; i > amount; i--) {
static if (op=="+") this--;
else this++;
}
}

T to(T)() const if(isNumeric!T) {
return cast(T)(b[0] + 2*b[1] + 4*b[2]);
}

T opCast(T)() if (isNumeric!T) {
return cast(T)(b[0] + 2*b[1] + 4*b[2]);
}

T to(T)() const if(is(T==string)) {
if (this==Direction.N) return "north";
else if (this==Direction.NE) return "northeast";
else if (this==Direction.E) return "east";
else if (this==Direction.SE) return "southeast";
else if (this==Direction.S) return "south";
else if (this==Direction.SW) return "southwest";
else if (this==Direction.W) return "west";
else if (this==Direction.NW) return "northwest";
else throw new Exception("Direction.to!: direction has a 
value that should be impossible.");

//else return ""; //This should never happen.
}

bool[3] opCast() const {
return this.b;
}

Direction opposite() const {
return Direction([b[0], b[1], !b[2]]);
}

bool diagonal() {
return b[0];
}

int getAngle() {
if (this==Direction.N) return 0;
else if (this==Direction.NE) return 45;
else if (this==Direction.E) return 90;
else if (this==Direction.SE) return 135;
else if (this==Direction.S) return 180;
else if (this==Direction.SW) return 225;
else if (this==Direction.W) return 270;
else if (this==Direction.NW) return 315;
else throw new Exception("Direction.getAngle: direction 
has a value that should be impossible.");

}
}
```

The one thing that cant be done on this is doing `direction+8`. 
Perhaps it would have been easier if I had chosen to store the 
value as a ubyte rather than an array of bools. While this is 
probably over-optimized given the large amount of memory in 
today's computers, I like it that it can never be an illegitimate 
value.


There's probably some trick I can use to make it easier to figure 
out the functions to do numerical operations on bits, but I don't 
know how best to cleanly represent this kind of thing in code. 
Maybe I need to look for examples of how it's already done.


I noticed among the options for overloading unary operations are 
the symbols "+" & "-". What operation is being overloaded with 
the function `ref Direction opUnary(string op:"+")(int amount)`?

Re: Challenge: Make a data type for holding one of 8 directions allowing increment and overflow

2024-03-13 Thread Salih Dincer via Digitalmars-d-learn


On Wednesday, 13 March 2024 at 10:27:49 UTC, Basile B. wrote:
The semantics of the operators are actually not as clear as 
that. What if you define


```d
enum Direction
{
N = 1, NE, S = 45, SW
}
```

?


Certainly! EnumMembers; can be used. The EnumMembers template 
from the std.traits module is used to retrieve all the members of 
an enumeration. It generates a tuple containing all the 
enumeration values, which can be iterated over using a foreach 
loop. In the D programming language, you can use EnumMembers to 
iterate over enum values at compile time, which is useful for 
generating code based on enum members.

Here’s a simple code example:

```d
 enum Days
 {
   Monday= 1001,
   Tuesday   = 1010,
   Wednesday = 1011,
   Thursday  = 1100,
   Friday= 1101,
   Saturday  = 1110,
   Sunday= 
 }

 import std.traits : EnumMembers;
 foreach(day; EnumMembers!Days)
   day.writeln(":", cast(int)day);
```

SDB@79

Re: Challenge: Make a data type for holding one of 8 directions allowing increment and overflow

2024-03-13 Thread Basile B. via Digitalmars-d-learn


On Tuesday, 12 March 2024 at 05:38:03 UTC, Liam McGillivray wrote:
I am in need of a data type for holding direction information; 
one of 8 directions on a single axis. They are named in terms 
of compass directions. If D had a 4-bit datatype, I would just 
use this and do `+=2` whenever I want to change the datatype, 
but it doesn't.


Perhaps this would be a good programming challenge for someone 
more experienced than me. Make a data type (probably a struct) 
for holding one of 8 directional values using 3 bits. It should 
accept the use of increment operators to change the angle.


Ideally (but optionally), it should work as an enum of the same 
name; "Direction".


Here's a unittest that it should ideally pass:
```
unittest
{
Direction direction = Direction.N;
direction++;
assert(direction == Direction.NE);
direction+=3;
assert(direction == Direction.S);
direction--;
assert(direction == Direction.SE);
direction-=4;
assert(direction == Direction.NW);
}
```


While there are workarounds (as proposed in the other answers, 
using operator overloads) I tend to think that the way currently 
enums work with arithmetic operators is a symptom of an 
incomplete type-system. Enums made of integer numbers are sub 
classes of the parent [integral 
sequence](https://en.wikipedia.org/wiki/Integer_sequence).


The semantics of the operators are actually not as clear as that. 
What if you define


```d
enum Direction
{
N = 1, NE, S = 45, SW
}
```

?

You directly see that the proposed workarounds dont work anymore.

There are natural numbers, sub-sets of natural numbers, unordered 
sequences, etc.
The type system does not represent that. Anyway, I dont blame D, 
plenty of languages have the exact same problem.

Re: Challenge: Make a data type for holding one of 8 directions allowing increment and overflow

2024-03-12 Thread Salih Dincer via Digitalmars-d-learn


On Tuesday, 12 March 2024 at 05:38:03 UTC, Liam McGillivray wrote:
Perhaps this would be a good programming challenge for someone 
more experienced than me. Make a data type (probably a struct) 
for holding one of 8 directional values using 3 bits. It should 
accept the use of increment operators to change the angle.


D is such a perfect language that you can do the features you 
mentioned and more. I also implemented the following during my 
rookie years:


```d
alias Direction = enumSet;
union enumSet(T)
{
  T e;

  alias e this;
  struct
  {
int i;

auto opUnary(string op: "++")()
  => i = i < e.max ? ++i : e.min;

auto opUnary(string op: "--")()
  => i = i > e.min ? --i : e.max;

auto opOpAssign(string op: "+")(int val)
{
  i += val;
  if(i > e.max) i -= e.max + 1;
}

auto opOpAssign(string op: "-")(int val)
{
  i -= val;
  if(i < e.min) i += e.max + 1;
}
  }

  string toString() const
=> e.to!string;
}

unittest
{
 auto direction = Direction!Directions(Directions.N);
 direction++;
 assert(direction == Directions.NE);
 direction+=3;
 assert(direction == Directions.S);
 direction--;
 assert(direction == Directions.SE);
 direction-=4;
 assert(direction == Directions.NW);
}

import std.stdio, std.conv;

void main()
{
  enum Directions
  {
N , NE , E, SE, S, SW , W, NW
  }

  auto test = enumSet!Directions(Directions.W);
   test += 9; /*

   ++test; ++test; ++test;
   ++test; ++test; ++test;
   ++test; ++test; ++test;//*/

   test.writeln;

   test--; test--;
   test.writeln;
}
```

Here union was used with an extra template parameter. I also 
added 2 aliases to avoid confusion.


SDB@79

Re: Challenge: Make a data type for holding one of 8 directions allowing increment and overflow

2024-03-12 Thread Richard (Rikki) Andrew Cattermole via Digitalmars-d-learn


On 13/03/2024 11:00 AM, Liam McGillivray wrote:
I'm not familiar with the syntax of the line |value &= 7;|. Is it 
equivalent to writing |value = value % 7;|?


& is a bitwise and.

LSB 123456789 MSB

& 7

LSB 12300 MSB

Anyway, you used an int, but I used an array of 3 bools. I'm guessing 
that mine uses less memory, but I'm not sure how memory it adds when 
it's a struct with functions.


Due to alignment, it'll probably use just as much.

Mine only needs a single ``byte``, at 7 bits it's more than enough.

But ``int`` doesn't make much difference unless you are packing 
instances together ``align(0):`` and realistically cpus are optimized 
for 32bits not 8.

Re: Challenge: Make a data type for holding one of 8 directions allowing increment and overflow

2024-03-12 Thread Liam McGillivray via Digitalmars-d-learn

On Tuesday, 12 March 2024 at 06:38:28 UTC, Richard (Rikki) Andrew 
Cattermole wrote:
By taking advantage of integer wrapping and a bitwise and, its 
quite a simple problem to solve!


Challenge for the reader: add support for binary operations and 
toString support.


https://dlang.org/spec/operatoroverloading.html

```d
struct Direction {
private int value;

Direction opUnary(string op:"++")() {
value++;
value &= 7;
return this;
}

Direction opUnary(string op:"--")() {
value--;
value &= 7;
return this;
}

void opOpAssign(string op:"+")(int amount) {
value += amount;
value &= 7;
}

void opOpAssign(string op:"-")(int amount) {
value -= amount;
value &= 7;
}

enum Direction N = Direction(0);
enum Direction NE = Direction(1);
enum Direction E = Direction(2);
enum Direction SE = Direction(3);
enum Direction S = Direction(4);
enum Direction SW = Direction(5);
enum Direction W = Direction(6);
enum Direction NW = Direction(7);
}

unittest {
 Direction direction = Direction.N;
 direction++;
 assert(direction == Direction.NE);
 direction+=3;
 assert(direction == Direction.S);
 direction--;
 assert(direction == Direction.SE);
 direction-=4;
 assert(direction == Direction.NW);
}
```


Interesting. I didn't know that an enum can be defined inside a 
struct like that. I had used functions to get around it.


Here is what I had already mostly written, using help from 
ChatGPT (but only for the opUnary syntax, not the algorithm):

```
struct Direction //One of 8 directions stored in 3 bits
{
bool[3] d;

static Direction N() { return 
Direction(d:[false,false,false]); }
static Direction NE() { return 
Direction(d:[false,false,true]); }
static Direction E() { return 
Direction(d:[false,true,false]); }
static Direction SE() { return 
Direction(d:[false,true,true]); }
static Direction S() { return 
Direction(d:[true,false,false]); }
static Direction SW() { return 
Direction(d:[true,false,true]); }
static Direction W() { return Direction(d:[true,true,false]); 
}
static Direction NW() { return Direction(d:[true,true,true]); 
}


ref Direction opUnary(string op)() if (op == "++" || op == 
"--") {

if (op == "++") const bool up = true;
else const bool up = false;

if (d[0]) {
if (d[1]) d[2] = !d[2];
d[1] = !d[1];
}
d[0] = !d[0];
return this;
}

auto to(T)() const {
return cast(T)(d[0] + 2*d[1] + 4*d[2]);
}
}
```

I am not entirely sure how well it works. I will come back later 
with an updated version with more functions.


I'm not familiar with the syntax of the line `value &= 7;`. Is it 
equivalent to writing `value = value % 7;`?


Anyway, you used an int, but I used an array of 3 bools. I'm 
guessing that mine uses less memory, but I'm not sure how memory 
it adds when it's a struct with functions.

Re: Challenge: Make a data type for holding one of 8 directions allowing increment and overflow

2024-03-12 Thread Richard (Rikki) Andrew Cattermole via Digitalmars-d-learn

By taking advantage of integer wrapping and a bitwise and, its quite a 
simple problem to solve!


Challenge for the reader: add support for binary operations and toString 
support.


https://dlang.org/spec/operatoroverloading.html

```d
struct Direction {
private int value;

Direction opUnary(string op:"++")() {
value++;
value &= 7;
return this;
}

Direction opUnary(string op:"--")() {
value--;
value &= 7;
return this;
}

void opOpAssign(string op:"+")(int amount) {
value += amount;
value &= 7;
}

void opOpAssign(string op:"-")(int amount) {
value -= amount;
value &= 7;
}

enum Direction N = Direction(0);
enum Direction NE = Direction(1);
enum Direction E = Direction(2);
enum Direction SE = Direction(3);
enum Direction S = Direction(4);
enum Direction SW = Direction(5);
enum Direction W = Direction(6);
enum Direction NW = Direction(7);
}

unittest {
 Direction direction = Direction.N;
 direction++;
 assert(direction == Direction.NE);
 direction+=3;
 assert(direction == Direction.S);
 direction--;
 assert(direction == Direction.SE);
 direction-=4;
 assert(direction == Direction.NW);
}
```

Challenge: Make a data type for holding one of 8 directions allowing increment and overflow

2024-03-11 Thread Liam McGillivray via Digitalmars-d-learn

I am in need of a data type for holding direction information; 
one of 8 directions on a single axis. They are named in terms of 
compass directions. If D had a 4-bit datatype, I would just use 
this and do `+=2` whenever I want to change the datatype, but it 
doesn't.


Perhaps this would be a good programming challenge for someone 
more experienced than me. Make a data type (probably a struct) 
for holding one of 8 directional values using 3 bits. It should 
accept the use of increment operators to change the angle.


Ideally (but optionally), it should work as an enum of the same 
name; "Direction".


Here's a unittest that it should ideally pass:
```
unittest
{
Direction direction = Direction.N;
direction++;
assert(direction == Direction.NE);
direction+=3;
assert(direction == Direction.S);
direction--;
assert(direction == Direction.SE);
direction-=4;
assert(direction == Direction.NW);
}
```

Re: The One Billion Row Challenge

2024-01-13 Thread Sergey via Digitalmars-d-learn


On Saturday, 13 January 2024 at 23:25:07 UTC, monkyyy wrote:

On Thursday, 11 January 2024 at 11:21:39 UTC, Sergey wrote:
On Thursday, 11 January 2024 at 08:57:43 UTC, Christian 
Köstlin wrote:

Did someone already try to do this in dlang?
I guess it will be very hard to beat the java solutions 
running with graalvm!


https://news.ycombinator.com/item?id=38851337

Kind regards,
Christian


I think C++ people already beated Java's performance 
https://github.com/buybackoff/1brc?tab=readme-ov-file#native


I feel we could beat c++ if they didn't radix sort


The project is very hard. Many optimizations and tricks were 
applied by others.
It requires a lot of skill to implement everything on a high 
level.

Re: The One Billion Row Challenge

2024-01-13 Thread monkyyy via Digitalmars-d-learn


On Thursday, 11 January 2024 at 11:21:39 UTC, Sergey wrote:
On Thursday, 11 January 2024 at 08:57:43 UTC, Christian Köstlin 
wrote:

Did someone already try to do this in dlang?
I guess it will be very hard to beat the java solutions 
running with graalvm!


https://news.ycombinator.com/item?id=38851337

Kind regards,
Christian


I think C++ people already beated Java's performance 
https://github.com/buybackoff/1brc?tab=readme-ov-file#native


I feel we could beat c++ if they didn't radix sort

Re: The One Billion Row Challenge

2024-01-11 Thread bachmeier via Digitalmars-d-learn

On Thursday, 11 January 2024 at 08:57:43 UTC, Christian Köstlin 
wrote:

Did someone already try to do this in dlang?
I guess it will be very hard to beat the java solutions running 
with graalvm!


https://news.ycombinator.com/item?id=38851337

Kind regards,
Christian


The problem with this challenge can be seen in the initial 
comments. Writing the fastest possible program *for a specific 
dataset* is not the same thing as writing the fastest program for 
an arbitrary dataset of that size. And, indeed, the fastest 
program is the one that does nothing but print the answer.


Speed on this task doesn't tell you anything about performance 
with different types/sizes of data or constraints on programmer 
time needed to produce a correct implementation and maintain it 
over time.

Re: The One Billion Row Challenge

2024-01-11 Thread Sergey via Digitalmars-d-learn

On Thursday, 11 January 2024 at 08:57:43 UTC, Christian Köstlin 
wrote:

Did someone already try to do this in dlang?
I guess it will be very hard to beat the java solutions running 
with graalvm!


https://news.ycombinator.com/item?id=38851337

Kind regards,
Christian


I think C++ people already beated Java's performance 
https://github.com/buybackoff/1brc?tab=readme-ov-file#native

Re: Threading challenge: calculate fib(45) while spinning

2021-10-16 Thread Sebastiaan Koppe via Digitalmars-d-learn


On Friday, 15 October 2021 at 03:35:44 UTC, jfondren wrote:
The book, "The Go Programming Language" has this simple 
goroutine example:


[...]


Here is a similar implementation using the concurrency library:

```d
import concurrency;
import concurrency.stream;
import concurrency.sender : justFrom;
import concurrency.operations : via, race;
import concurrency.thread : ThreadSender;
import core.time : msecs;
import std.stdio : writef, writefln, stdout;
import core.thread : Thread;

void main() @safe {
enum chars = `-\|/`;
auto spinner = infiniteStream(0)
.scan((int acc, int _) => acc + 1, 0)
.collect((int i) shared @trusted {
writef("\r%c", chars[i % chars.length]);
stdout.flush();
Thread.sleep(100.msecs);
})
.via(ThreadSender());

enum n = 45;
auto work = justFrom(() => fib(n));

auto result = race(spinner, work).syncWait.value;
writefln("\rFibonacci(%d) = %d", n, result.get);
}

int fib(int x) pure @safe @nogc {
if (x < 2)
return x;
return fib(x - 1) + fib(x - 2);
}
```

Go has language support so it is a bit unfair to compare it.

But this code will properly handle errors (in case `writef` or 
`flush` throws), and as well as having an explicit 
synchronization point so that the final `writeln` is always after 
the spinner is done.

Re: Threading challenge: calculate fib(45) while spinning

2021-10-15 Thread Steven Schveighoffer via Digitalmars-d-learn


On 10/15/21 10:01 AM, Ali Çehreli wrote:

 >    writefln!"\rFibonacci(%d) = %d"(n, fibN);

That '\r' bothered me because the actual work needs to know what the 
spinner is doing to clear its remaining character.


I would expect the original go code had the same problem.

-Steve

Re: Threading challenge: calculate fib(45) while spinning

2021-10-15 Thread Ali Çehreli via Digitalmars-d-learn

On 10/14/21 8:54 PM, Ali Çehreli wrote:

>writefln!"\rFibonacci(%d) = %d"(n, fibN);

That '\r' bothered me because the actual work needs to know what the 
spinner is doing to clear its remaining character.

>receiveTimeout(delay,
>   (OwnerTerminated msg) {

And there is a race condition because the spinner can print an extra 
character by the time it receives the OwnerTerminated message. (You can 
observe this by adding e.g. Thread.sleep(300.msecs) after the 
"\rFibonnacci..." line above.)

So, I improved it by removing both of those concerns as well as adding 
the following:

- An optional message when spinning (it can be further improved because 
there is an extra space character if the message is empty)

- A withSpinner() function to work with any delegate

The only requirement is that the delegate should not output to stdout if 
we want a clean output.

import std.stdio : stdout, writef, writefln;
import std.concurrency : receiveTimeout, send, spawn;
import std.traits : ReturnType;
import core.thread : Duration, msecs, Thread;
import std.range : cycle, repeat, walkLength;
import std.format : format;

void main() {
  enum n = 45;

  int fibN; // Left mutable not to complicate the example

  withSpinner({
  fibN = fib(n); // slow
},
format!"Calculating fib(%s)"(n));

  writefln!"Fibonacci(%d) = %d"(n, fibN);
}

// The delegate 'dg' should not output to stdout.
void withSpinner(Dg)(Dg dg,
 string message = null,
 Duration delay = 100.msecs) {
  shared(bool) spinnerDone = false;
  auto s = spawn(, message, delay, );

  // Do work while spinning
  dg();

  // Tell the spinner to stop (the value does not matter)
  s.send(0x0FF);

  // Busy(ish) wait until the spinner is done
  while (!spinnerDone) {
Thread.yield();
  }
}

void spinner(string message,
 Duration delay,
 shared(bool) * done) {
  foreach (c; `-\|/`.cycle) {
if (receiveTimeout(delay, (int _) {})) {
  // Stop request received

  // Clear the spinning message
  writef("\r%s  \r", " ".repeat(walkLength(message)));

  // Tell the user we are done
  *done = true;
  return;
}
writef!"\r%s %c"(message, c);
stdout.flush();
  }
}

auto fib(int x) {
  if (x < 2) {
return x;
  }
  return fib(x-1) + fib(x-2);
}

Ali

Re: Threading challenge: calculate fib(45) while spinning

2021-10-15 Thread Steven Schveighoffer via Digitalmars-d-learn


On 10/14/21 11:35 PM, jfondren wrote:

The book, "The Go Programming Language" has this simple goroutine example:

```go
func main() {
     go spinner(100 * time.Millisecond)
     const n = 45
     fibN := fib(n) // slow
     fmt.Printf("\rFibonacci(%d) = %d\n", n, fibN)
}

func spinner(delay time.Duration) {
     for {
     for _, r := range `-\|/` {
     fmt.Printf("\r%c", r)
     time.Sleep(delay)
     }
     }
}

func fib(x int) int {
     if x < 2 {
     return x
     }
     return fib(x-1) + fib(x-2)
}
```

Attempt #1, with std.concurrency:

```d
import std.concurrency : spawn;
import core.thread : Thread;
import std.stdio : writefln, writef, stdout;
import std.datetime : msecs, Duration;

void main() @safe {
     (() @trusted { spawn(, 100.msecs); })();
     const n = 45;
     const fibN = fib(n); // slow
     writefln!"\rFibonacci(%d) = %d"(n, fibN);
}

void spinner(Duration delay) @safe {
     (() @trusted { Thread.getThis.isDaemon(true); })();
     while (true) {
     foreach (char c; `-\|/`) {
     writef!"\r%c"(c);
     (() @trusted { stdout.flush; })();
     (() @trusted { Thread.sleep(delay); })();
     }
     }
}

int fib(int x) pure @safe @nogc {
     if (x < 2)
     return x;
     return fib(x - 1) + fib(x - 2);
}
```

This version has two problems:

1. a race condition with `isDaemon`: if `main()` ends before 
`isDaemon(true)` is called, then the program never ends because the 
kill-non-daemon-threads module destructor is called while the new thread 
isn't a daemon thread.


You can also just spawn a thread directly with `Thread`, which I believe 
allows you to set the daemon-ness from `main`.




2. it crashes about 10% of the time on exit (in dmd, gdc, and ldc). 
valgrind on a gdc build complains about "Conditional jump or move 
depends on uninitialised value(s)" early on.



The crash is likely because you are using D i/o utilities, and the 
runtime is shut down. Technically it shouldn't cause a problem, but 
possibly there are things that are needed deep inside `writef`.


If you switch to `printf`, it will probably work.

-Steve

Re: Threading challenge: calculate fib(45) while spinning

2021-10-15 Thread Imperatorn via Digitalmars-d-learn


On Friday, 15 October 2021 at 03:54:17 UTC, Ali Çehreli wrote:

On 10/14/21 8:35 PM, jfondren wrote:

[...]


Here is one that uses receiveTimeout and OwnerTerminated:

import std.stdio;
import std.concurrency;
import core.thread;

void main() {
  spawnLinked(, 100.msecs);
  enum n = 45;
  const fibN = fib(n); // slow
  writefln!"\rFibonacci(%d) = %d"(n, fibN);
}

void spinner(const(Duration) delay) {
  for (;;) {
foreach (r; `-\|/`) {
  writef!"\r%c"(r);
  stdout.flush();
  bool done;
  receiveTimeout(delay,
 (OwnerTerminated msg) {
   done = true;
 });
  if (done) {
return;
  }
}
  }
}

auto fib(int x) {
  if (x < 2) {
return x;
  }
  return fib(x-1) + fib(x-2);
}

Ali


This is a "similar" approach to what Erlang does. I have always 
liked it ☀️

Re: Threading challenge: calculate fib(45) while spinning

2021-10-14 Thread Ali Çehreli via Digitalmars-d-learn


On 10/14/21 9:17 PM, jfondren wrote:

On Friday, 15 October 2021 at 03:54:17 UTC, Ali Çehreli wrote:

On 10/14/21 8:35 PM, jfondren wrote:
The book, "The Go Programming Language" has this simple goroutine 
example:


Here is one that uses receiveTimeout and OwnerTerminated:



Very nice, replacing Thread.sleep with receiveTimeout and getting 
graceful interruption for free. This also doesn't crash.


Cool. :)

Actually, it can be shorter by checking the return value of receiveTimeout:

  if (receiveTimeout(delay, (OwnerTerminated msg) {})) {
return;
  }

I didn't use this method earlier because I was afraid an unexpected 
message might make receiveTimeout return 'true'. But I've tested just 
now: Only the expected OwnerTerminated makes it return 'true'.


Ali

Re: Threading challenge: calculate fib(45) while spinning

2021-10-14 Thread jfondren via Digitalmars-d-learn


On Friday, 15 October 2021 at 03:54:17 UTC, Ali Çehreli wrote:

On 10/14/21 8:35 PM, jfondren wrote:
The book, "The Go Programming Language" has this simple 
goroutine example:


Here is one that uses receiveTimeout and OwnerTerminated:



Very nice, replacing Thread.sleep with receiveTimeout and getting 
graceful interruption for free. This also doesn't crash.

Re: Threading challenge: calculate fib(45) while spinning

2021-10-14 Thread Ali Çehreli via Digitalmars-d-learn


On 10/14/21 8:35 PM, jfondren wrote:

The book, "The Go Programming Language" has this simple goroutine example:


Here is one that uses receiveTimeout and OwnerTerminated:

import std.stdio;
import std.concurrency;
import core.thread;

void main() {
  spawnLinked(, 100.msecs);
  enum n = 45;
  const fibN = fib(n); // slow
  writefln!"\rFibonacci(%d) = %d"(n, fibN);
}

void spinner(const(Duration) delay) {
  for (;;) {
foreach (r; `-\|/`) {
  writef!"\r%c"(r);
  stdout.flush();
  bool done;
  receiveTimeout(delay,
 (OwnerTerminated msg) {
   done = true;
 });
  if (done) {
return;
  }
}
  }
}

auto fib(int x) {
  if (x < 2) {
return x;
  }
  return fib(x-1) + fib(x-2);
}

Ali

Threading challenge: calculate fib(45) while spinning

2021-10-14 Thread jfondren via Digitalmars-d-learn

The book, "The Go Programming Language" has this simple goroutine 
example:


```go
func main() {
go spinner(100 * time.Millisecond)
const n = 45
fibN := fib(n) // slow
fmt.Printf("\rFibonacci(%d) = %d\n", n, fibN)
}

func spinner(delay time.Duration) {
for {
for _, r := range `-\|/` {
fmt.Printf("\r%c", r)
time.Sleep(delay)
}
}
}

func fib(x int) int {
if x < 2 {
return x
}
return fib(x-1) + fib(x-2)
}
```

Attempt #1, with std.concurrency:

```d
import std.concurrency : spawn;
import core.thread : Thread;
import std.stdio : writefln, writef, stdout;
import std.datetime : msecs, Duration;

void main() @safe {
(() @trusted { spawn(, 100.msecs); })();
const n = 45;
const fibN = fib(n); // slow
writefln!"\rFibonacci(%d) = %d"(n, fibN);
}

void spinner(Duration delay) @safe {
(() @trusted { Thread.getThis.isDaemon(true); })();
while (true) {
foreach (char c; `-\|/`) {
writef!"\r%c"(c);
(() @trusted { stdout.flush; })();
(() @trusted { Thread.sleep(delay); })();
}
}
}

int fib(int x) pure @safe @nogc {
if (x < 2)
return x;
return fib(x - 1) + fib(x - 2);
}
```

This version has two problems:

1. a race condition with `isDaemon`: if `main()` ends before 
`isDaemon(true)` is called, then the program never ends because 
the kill-non-daemon-threads module destructor is called while the 
new thread isn't a daemon thread.


2. it crashes about 10% of the time on exit (in dmd, gdc, and 
ldc). valgrind on a gdc build complains about "Conditional jump 
or move depends on uninitialised value(s)" early on.


Attempt #2, with std.parallelism:

```d
import std.parallelism : task, taskPool;
import core.thread : Thread;
import std.stdio : writefln, writef, stdout;
import std.datetime : msecs, Duration;

void main() @safe {
auto spin = task!spinner(100.msecs);
taskPool.put(spin);
const n = 45;
const fibN = fib(n); // slow
writefln!"\rFibonacci(%d) = %d"(n, fibN);
}

void spinner(Duration delay) @safe {
while (true) {
foreach (char c; `-\|/`) {
writef!"\r%c"(c);
(() @trusted { stdout.flush; })();
(() @trusted { Thread.sleep(delay); })();
}
}
}

int fib(int x) pure @safe @nogc {
if (x < 2)
return x;
return fib(x - 1) + fib(x - 2);
}
```

This version continues to spin after the Fibonacci result is 
printed, despite 
https://dlang.org/phobos/std_parallelism.html#.taskPool saying 
that `taskPool` worker threads are daemon by default, and despite 
various attempts to add `isDaemon(true)` calls.


Is there a d version without these problems, and without varying 
substantially from the go (by e.g. having the spinner poll to see 
if it should exit gracefully).

Re: Bit rotation question/challenge

2021-01-30 Thread vitamin via Digitalmars-d-learn


On Saturday, 30 January 2021 at 14:56:14 UTC, burt wrote:

On Saturday, 30 January 2021 at 14:41:59 UTC, Afgdr wrote:

On Saturday, 30 January 2021 at 14:40:49 UTC, Afgdr wrote:

On Saturday, 30 January 2021 at 13:30:49 UTC, burt wrote:

[...]


cast as uint and shift. cast the result as ubyte[4].


obiously, that works for n=4 with uint and n=8 for ulong, only.


Yes I used to do this, but then I needed it for n > 8.


You can try somethink like this:

https://run.dlang.io/is/POQgnb

import std.range : cycle, take, drop;
import std.algorithm : copy;
import std.stdio;

version (LittleEndian)
ubyte[n] rotateRight(size_t n)(ref const ubyte[n] array, uint 
rotation){

typeof(return) result;

array[]
.cycle()
.drop(n - (rotation / 8) % n)
.take(n)
.copy(result[]);

const ubyte bit_rotation = rotation % 8;

enum ubyte full = 0b_;

if(bit_rotation == 0)
return result;

ubyte next_prefix(const ubyte elm){
const ubyte suffix = (elm & ~(full << bit_rotation));
const ubyte prefix = cast(ubyte)(suffix << (8 - 
bit_rotation));

return prefix;
}

ubyte prefix = next_prefix(result[$-1]);

foreach(ref ubyte elm; result[]){
const new_prefix = next_prefix(elm);
elm = (elm >> bit_rotation) | prefix;
prefix = new_prefix;
}

return result;
}

void main(){
ubyte[4] x = [
0b00011000,
0b0011,
0b00010101,
0b0010,
];

writefln!"%(%8b,\n%)"(x.rotateRight(4));
}

Re: Bit rotation question/challenge

2021-01-30 Thread Afgdr via Digitalmars-d-learn


On Saturday, 30 January 2021 at 14:56:14 UTC, burt wrote:

On Saturday, 30 January 2021 at 14:41:59 UTC, Afgdr wrote:

On Saturday, 30 January 2021 at 14:40:49 UTC, Afgdr wrote:

On Saturday, 30 January 2021 at 13:30:49 UTC, burt wrote:

[...]


cast as uint and shift. cast the result as ubyte[4].


obiously, that works for n=4 with uint and n=8 for ulong, only.


Yes I used to do this, but then I needed it for n > 8.


As suggested in the other answer BitArray may be the best generic 
solution.

Re: Bit rotation question/challenge

2021-01-30 Thread burt via Digitalmars-d-learn


On Saturday, 30 January 2021 at 14:41:59 UTC, Afgdr wrote:

On Saturday, 30 January 2021 at 14:40:49 UTC, Afgdr wrote:

On Saturday, 30 January 2021 at 13:30:49 UTC, burt wrote:

[...]


cast as uint and shift. cast the result as ubyte[4].


obiously, that works for n=4 with uint and n=8 for ulong, only.


Yes I used to do this, but then I needed it for n > 8.

Re: Bit rotation question/challenge

2021-01-30 Thread burt via Digitalmars-d-learn


On Saturday, 30 January 2021 at 14:17:06 UTC, Paul Backus wrote:

On Saturday, 30 January 2021 at 13:30:49 UTC, burt wrote:

[...]

Now I want to bit-rotate the array as if it is one big integer.


You may find `std.bitmanip.BitArray` useful for this:

http://phobos.dpldocs.info/std.bitmanip.BitArray.html


Thank you, this is indeed what I am looking for!

For future reference, this is how I implemented it:

```d
ubyte[n] rotateRight(size_t n)(ubyte[n] x, uint rotation)
{
import std.bitmanip : BitArray;

ubyte[n] x2;
foreach (i, value; x) // have to swap because of endianness
x2[n - 1 - i] = value;

auto copy = x2;

auto bitArray1 = BitArray(cast(void[]) x2[], n * 8);
auto bitArray2 = BitArray(cast(void[]) copy[], n * 8);
bitArray1 >>= rotation;
bitArray2 <<= n * 8 - rotation;
bitArray1 |= bitArray2;

foreach (i, value; x2) // swap back
x[n - 1 - i] = value;
return x;
}

ubyte[4] x = [
0b00011000,
0b0011,
0b00010101,
0b0010,
];
writefln!"%(%8b,\n%)"(x.rotateRight(4));
```

Re: Bit rotation question/challenge

2021-01-30 Thread Afgdr via Digitalmars-d-learn


On Saturday, 30 January 2021 at 14:40:49 UTC, Afgdr wrote:

On Saturday, 30 January 2021 at 13:30:49 UTC, burt wrote:

I have a static array of `ubyte`s of arbitrary size:

```d
ubyte[4] x = [ // in reality, ubyte[64]
0b1000,
0b0001,
0b00010101,
0b0010,
];
```

Now I want to bit-rotate the array as if it is one big 
integer. So:


```d
ubyte[n] rotateRight(size_t n)(ref const ubyte[n] array, uint 
rotation)

{
// ?
}
// same for rotateLeft

ubyte[4] y = [
0b1001,
0b0100,
0b,
0b10001010,
];
assert(x.rotateRight(9) == y);
assert(y.rotateLeft(9) == x);
```

Any ideas how this could be achieved? I.e. what should go at 
the "?" for rotateRight and rotateLeft?


cast as uint and shift. cast the result as ubyte[4].


obiously, that works for n=4 with uint and n=8 for ulong, only.

Re: Bit rotation question/challenge

2021-01-30 Thread Afgdr via Digitalmars-d-learn


On Saturday, 30 January 2021 at 13:30:49 UTC, burt wrote:

I have a static array of `ubyte`s of arbitrary size:

```d
ubyte[4] x = [ // in reality, ubyte[64]
0b1000,
0b0001,
0b00010101,
0b0010,
];
```

Now I want to bit-rotate the array as if it is one big integer. 
So:


```d
ubyte[n] rotateRight(size_t n)(ref const ubyte[n] array, uint 
rotation)

{
// ?
}
// same for rotateLeft

ubyte[4] y = [
0b1001,
0b0100,
0b,
0b10001010,
];
assert(x.rotateRight(9) == y);
assert(y.rotateLeft(9) == x);
```

Any ideas how this could be achieved? I.e. what should go at 
the "?" for rotateRight and rotateLeft?


cast as uint and shift. cast the result as ubyte[4].

Re: Bit rotation question/challenge

2021-01-30 Thread Paul Backus via Digitalmars-d-learn


On Saturday, 30 January 2021 at 13:30:49 UTC, burt wrote:

I have a static array of `ubyte`s of arbitrary size:

```d
ubyte[4] x = [ // in reality, ubyte[64]
0b1000,
0b0001,
0b00010101,
0b0010,
];
```

Now I want to bit-rotate the array as if it is one big integer.


You may find `std.bitmanip.BitArray` useful for this:

http://phobos.dpldocs.info/std.bitmanip.BitArray.html

Bit rotation question/challenge

2021-01-30 Thread burt via Digitalmars-d-learn


I have a static array of `ubyte`s of arbitrary size:

```d
ubyte[4] x = [ // in reality, ubyte[64]
0b1000,
0b0001,
0b00010101,
0b0010,
];
```

Now I want to bit-rotate the array as if it is one big integer. 
So:


```d
ubyte[n] rotateRight(size_t n)(ref const ubyte[n] array, uint 
rotation)

{
// ?
}
// same for rotateLeft

ubyte[4] y = [
0b1001,
0b0100,
0b,
0b10001010,
];
assert(x.rotateRight(9) == y);
assert(y.rotateLeft(9) == x);
```

Any ideas how this could be achieved? I.e. what should go at the 
"?" for rotateRight and rotateLeft?

Challenge

2020-05-09 Thread Jack Applegame via Digitalmars-d-learn


I recently came across an interesting exercise.

Given a series of positive numbers, each of which belongs to the 
set


{ 2^^i * 3^^j * 5^^k | i, j, k ≥ 0 }.

The series is ordered in ascending order. The beginning looks 
like this:


{ 1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, 16, 18, 20, 24, ... }

The goal is to get the Nth element of the series. For example, 
for N = 10, the answer is 12.


On the Internet, I found an elegant and incredibly fast solution 
in Haskell:


```
mergeUniq :: Ord a => [a] -> [a] -> [a]
mergeUniq (x:xs) (y:ys) = case x `compare` y of
   EQ -> x : mergeUniq xs ys
   LT -> x : mergeUniq xs (y:ys)
   GT -> y : mergeUniq (x:xs) ys

powers :: [Integer]
powers = 1 : expand 2 `mergeUniq` expand 3 `mergeUniq` expand 5
  where
expand factor = (factor *) <$> powers

main = print $ powers!!99
```
On my machine, the 100th element is found in 0.215s. OMG!


After that, I spent almost the entire day searching for at least 
the same fast solution in D.


My first attempt was simple and quite pretty, but awfully slow:

```
import std.stdio;
import std.array;
import std.bigint;
import std.algorithm;

auto generate(int n) {
BigInt[] nums = [BigInt("1")];
foreach(i; 0..n) {
nums = merge(nums, [nums[i] * 2, nums[i] * 3, nums[i] * 
5]).uniq().array();

}
return nums[n - 1];
}

void main() {
  writeln(generate(5000));
}
```

0.275s for 5000th element.

At the end of the day, I managed to catch up and even overtake 
Haskell by emulating its lazyness with ranges and a funny trick.


Victory! :)

If you find this interesting, I will publish my latest version.
And feel free to find your own solution. ;)

1 2 3 4 5 6 7 >

1 - 100 of 658 matches

Mail list logo