11 ms·

Beautiful Binary Search in D

72 points by alex_muscar 4y ago

alex_muscar 4y ago
Where I use D's metaprogramming capabilities to generate a binary search function using Shar's algorithm.
wood_spirit 4y ago
Can Shar’s unrolling be combined with Duff’s device to work on any size of dynamic array? And how would it perform?
gavinray 4y ago
D is the systems language I enjoy writing the most out of C++, Rust, and Go. It feels a lot like a mix between C# and JS, but at the low level access of C++. It has a lot of unique features but the "killer feature" by far for me is Contract Programming and Invariants https://tour.dlang.org/tour/en/gems/contract-programming https://tour.dlang.org/tour/en/gems/contract-programming Invariants changed my life, so much so that I built a GCC plugin to add them to C++ It used to be the case that the developer tooling wasn't very good, but the "code-d" VS Code plugin has matured greatly in the last few years and has some features you won't find even in bigger languages (Like the ability to colorize source code lines with GC profiling info or test coverage status) --- Another useful bit of info is that AddressSanitizer and tools like LLVM libFuzzer work with the LDC compiler
- agumonkey 4y ago
  Is your gcc plugin a personal project or something you built for a team ? I find the idea brilliant in itself but I wonder if other people felt the need, and uses / enjoy this kind of improvements. I want to add profile/coverage info in emacs now :) D is a strange point in PL landscape, it's been here for ages, never took off (for some value of taking off) even though it seems there's a lot to like.
  - gavinray 4y ago
    It was a small personal project, I posted about it here some months ago fwiw: https://news.ycombinator.com/item?id=34211482 https://news.ycombinator.com/item?id=34211482 D has no (FAANG) corporate sponsor and it does all things well/has no particular speciality, these two things make it hard to compete with marketing of other languages I think There's a small but dedicated and active community
    - agumonkey 4y ago
      > does all things well a great feature IMO, helps communication in large teams I believe (in the imaginary world where teams use D :) thanks for the link, have the best day
      - mhh__ 4y ago
        This world is not imaginary
        agumonkey 4y ago
        Even better then :) Maybe it's like some languages that don't chase growth/viral/visibility but exist calmly doing work.
      - gavinray 4y ago
        I mean to say it's sort of a solid general purpose language/jack of all trades, with no particular speciality or thing it's deficient at
  - pjmlp 4y ago
    D has suffered from lack of corporate sponsor, and there were a couple of reboots trying to chase the next big thing that would bring more people in, this allowed other language ecosystems to improve their shortcomings, thus reducing the distance in language features. From my point of view in systems programming, experience with Oberon back in the day and such, I would really like that we would be talking more about D and less about Rust and Go, but unfortunately it isn't how things went.
- deleted 4y ago
  [deleted]
skocznymroczny 4y ago
Unless I am missing something, you can just use .length on a static array: int[5] a = [1,2,3,4,5]; writeln(a.length); // 5
- smcl 4y ago
  Is that available at compile time, though?
  - mhh__ 4y ago
    Yes
    - smcl 4y ago
      Oh neat, I'm still a dlang noob and only used it in Crafting Interpreters :)
- alex_muscar 4y ago
  Someone on the D subreddit pointed that out as well. I didn't know it was available at compile time. I'll update the post. Thanks.
theodpHN 4y ago
Beauty is in the eye of the beholder. While clever, this is (IMO) far less understandable and more error-prone than say COBOL's positively ancient built-in SEARCH ALL binary search statement. Here's an example of a 3-key binary table search from IBM's COBOL documentation that includes options for found and not found conditions. SEARCH ALL TABLE-ENTRY AT END PERFORM NOENTRY WHEN KEY-1 (INDX-1) = VALUE-1 AND KEY-2 (INDX-1) = VALUE-2 AND KEY-3 (INDX-1) = VALUE-3 MOVE PART-1 (INDX-1) TO OUTPUT-AREA END-SEARCH https://www.ibm.com/docs/en/cobol-zos/6.1?topic=all-example-binary-search https://www.ibm.com/docs/en/cobol-zos/6.1?topic=all-example-...
- 2h 4y ago
  Agree. This just screams of being too clever. It's OK to repeat things sometimes. If you DRY to the point that the code is not even readable, is that really an improvement? Also I physically shuddered when I saw the word template. Did no one learn from C++ mistakes?
  - mhh__ 4y ago
    > Did no one learn from C++ mistakes? D was designed by Walter Bright (who played a large role in inflicting C++ on the world) and Andrei Alexandrescu so you could say that...
    - ternaryoperator 4y ago
      > D was designed by Walter Bright (who played a large role in inflicting C++ on the world) That's a rather unfair characterization. He wrote the Datalight/Zortech C++ compiler. He was never--that I recall--a big flag-waver for C++.
      - mhh__ 4y ago
        His company originally was a C++ toolchain shop. Anyway, I was joking — Walter did one of the first (if not the first?) "Proper" C++ compilers, so the idea of not learning from C++ is rather ironic.
kazinator 4y ago
Reminds me of https://en.wikipedia.org/wiki/Successive-approximation_ADC https://en.wikipedia.org/wiki/Successive-approximation_ADC
deleted 4y ago
[deleted]
Kukumber 4y ago
D is a refreshing language in the sea of "alternative to C languages", they didn't reinvent the syntax, so if you come from C, using D will feel very natural and at home! (and you'll be protected from most unsafe/ub quirks of C) When it comes to metaprogramming, it's excellent, but it is a double edged sword, it can be useful, but if abused it'll tank your build speed, so one must find a proper balance to avoid pain later One of the few languages that offers its own backend! (LLVM/GCC backends are also available) I love this level of independence, a real labor of love, one of the best better C, i'd even say this is the evolution C needed
- Kranar 4y ago
  D isn't a good substitute for C due to its garbage collector. Yes, people always chime in about how you can disable D's garbage collector, but then you're stuck with an awkward language that lacks support for basic things like exceptions, closures, strings, slices, and a host of other features not to mention pretty much any third party library. If you are willing to accept a GC then D might be a good choice, if you find it fun then by all means go for it, but it's no longer so clear cut at that point given the wealth of GC'd programming languages available.
  - Kukumber 4y ago
    That's 100% bullshit You can ignore the GC or totally suppress it with @nogc or even not even link it with -betterC flag Having the GC optional is nice since you no longer need to use a scripting language to do your cli tools or utilities, it's there and well integrated If you are a proper developer who care about speed and fast code, you'll want to develop your own STL anyways, just like C/C++ are already doing, just like Rust people are also doing to get faster compile speed, D gives C/C++ interop as well as full C11 compiler So it's the perfect evolution of C, since it can compile and consume its ecosystem You can even consume python and rust libraries, wgpu works great with D

72 points by alex_muscar 4y ago

alex_muscar 4y ago

Where I use D's metaprogramming capabilities to generate a binary search function using Shar's algorithm.

wood_spirit 4y ago

Can Shar’s unrolling be combined with Duff’s device to work on any size of dynamic array? And how would it perform?

gavinray 4y ago

D is the systems language I enjoy writing the most out of C++, Rust, and Go. It feels a lot like a mix between C# and JS, but at the low level access of C++. It has a lot of unique features but the "killer feature" by far for me is Contract Programming and Invariants https://tour.dlang.org/tour/en/gems/contract-programming https://tour.dlang.org/tour/en/gems/contract-programming Invariants changed my life, so much so that I built a GCC plugin to add them to C++ It used to be the case that the developer tooling wasn't very good, but the "code-d" VS Code plugin has matured greatly in the last few years and has some features you won't find even in bigger languages (Like the ability to colorize source code lines with GC profiling info or test coverage status) --- Another useful bit of info is that AddressSanitizer and tools like LLVM libFuzzer work with the LDC compiler

agumonkey 4y ago
Is your gcc plugin a personal project or something you built for a team ? I find the idea brilliant in itself but I wonder if other people felt the need, and uses / enjoy this kind of improvements. I want to add profile/coverage info in emacs now :) D is a strange point in PL landscape, it's been here for ages, never took off (for some value of taking off) even though it seems there's a lot to like.
- gavinray 4y ago
  It was a small personal project, I posted about it here some months ago fwiw: https://news.ycombinator.com/item?id=34211482 https://news.ycombinator.com/item?id=34211482 D has no (FAANG) corporate sponsor and it does all things well/has no particular speciality, these two things make it hard to compete with marketing of other languages I think There's a small but dedicated and active community
  - agumonkey 4y ago
    > does all things well a great feature IMO, helps communication in large teams I believe (in the imaginary world where teams use D :) thanks for the link, have the best day
    - mhh__ 4y ago
      This world is not imaginary
      - agumonkey 4y ago
        Even better then :) Maybe it's like some languages that don't chase growth/viral/visibility but exist calmly doing work.
    - gavinray 4y ago
      I mean to say it's sort of a solid general purpose language/jack of all trades, with no particular speciality or thing it's deficient at
- pjmlp 4y ago
  D has suffered from lack of corporate sponsor, and there were a couple of reboots trying to chase the next big thing that would bring more people in, this allowed other language ecosystems to improve their shortcomings, thus reducing the distance in language features. From my point of view in systems programming, experience with Oberon back in the day and such, I would really like that we would be talking more about D and less about Rust and Go, but unfortunately it isn't how things went.
deleted 4y ago
[deleted]

skocznymroczny 4y ago

Unless I am missing something, you can just use .length on a static array: int[5] a = [1,2,3,4,5]; writeln(a.length); // 5

smcl 4y ago
Is that available at compile time, though?
- mhh__ 4y ago
  Yes
  - smcl 4y ago
    Oh neat, I'm still a dlang noob and only used it in Crafting Interpreters :)
alex_muscar 4y ago
Someone on the D subreddit pointed that out as well. I didn't know it was available at compile time. I'll update the post. Thanks.

theodpHN 4y ago

Beauty is in the eye of the beholder. While clever, this is (IMO) far less understandable and more error-prone than say COBOL's positively ancient built-in SEARCH ALL binary search statement. Here's an example of a 3-key binary table search from IBM's COBOL documentation that includes options for found and not found conditions. SEARCH ALL TABLE-ENTRY AT END PERFORM NOENTRY WHEN KEY-1 (INDX-1) = VALUE-1 AND KEY-2 (INDX-1) = VALUE-2 AND KEY-3 (INDX-1) = VALUE-3 MOVE PART-1 (INDX-1) TO OUTPUT-AREA END-SEARCH https://www.ibm.com/docs/en/cobol-zos/6.1?topic=all-example-binary-search https://www.ibm.com/docs/en/cobol-zos/6.1?topic=all-example-...

2h 4y ago
Agree. This just screams of being too clever. It's OK to repeat things sometimes. If you DRY to the point that the code is not even readable, is that really an improvement? Also I physically shuddered when I saw the word template. Did no one learn from C++ mistakes?
- mhh__ 4y ago
  > Did no one learn from C++ mistakes? D was designed by Walter Bright (who played a large role in inflicting C++ on the world) and Andrei Alexandrescu so you could say that...
  - ternaryoperator 4y ago
    > D was designed by Walter Bright (who played a large role in inflicting C++ on the world) That's a rather unfair characterization. He wrote the Datalight/Zortech C++ compiler. He was never--that I recall--a big flag-waver for C++.
    - mhh__ 4y ago
      His company originally was a C++ toolchain shop. Anyway, I was joking — Walter did one of the first (if not the first?) "Proper" C++ compilers, so the idea of not learning from C++ is rather ironic.

kazinator 4y ago

Reminds me of https://en.wikipedia.org/wiki/Successive-approximation_ADC https://en.wikipedia.org/wiki/Successive-approximation_ADC

deleted 4y ago

[deleted]

Kukumber 4y ago

D is a refreshing language in the sea of "alternative to C languages", they didn't reinvent the syntax, so if you come from C, using D will feel very natural and at home! (and you'll be protected from most unsafe/ub quirks of C) When it comes to metaprogramming, it's excellent, but it is a double edged sword, it can be useful, but if abused it'll tank your build speed, so one must find a proper balance to avoid pain later One of the few languages that offers its own backend! (LLVM/GCC backends are also available) I love this level of independence, a real labor of love, one of the best better C, i'd even say this is the evolution C needed

Kranar 4y ago
D isn't a good substitute for C due to its garbage collector. Yes, people always chime in about how you can disable D's garbage collector, but then you're stuck with an awkward language that lacks support for basic things like exceptions, closures, strings, slices, and a host of other features not to mention pretty much any third party library. If you are willing to accept a GC then D might be a good choice, if you find it fun then by all means go for it, but it's no longer so clear cut at that point given the wealth of GC'd programming languages available.
- Kukumber 4y ago
  That's 100% bullshit You can ignore the GC or totally suppress it with @nogc or even not even link it with -betterC flag Having the GC optional is nice since you no longer need to use a scripting language to do your cli tools or utilities, it's there and well integrated If you are a proper developer who care about speed and fast code, you'll want to develop your own STL anyways, just like C/C++ are already doing, just like Rust people are also doing to get faster compile speed, D gives C/C++ interop as well as full C11 compiler So it's the perfect evolution of C, since it can compile and consume its ecosystem You can even consume python and rust libraries, wgpu works great with D