Beautiful Binary Search in D

https://muscar.eu/shar-binary-search-meta.html

by alex_muscar • 3 years ago

72 59 3 years ago

muscar.eu

alex_muscar3• 3 years ago

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

wood_spirit• 3 years ago

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

gavinray6• 3 years 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

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

agumonkey3• 3 years 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.

gavinray6• 3 years ago

It was a small personal project, I posted about it here some months ago fwiw:

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

pjmlp2• 3 years 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.

dataflow11• 3 years ago

D never took off IMO because you can't abstract away a GC. The moment your callees rely on a GC, you have no choice but to have one in your program. The idea that you can avoid it in practice just because the language doesn't mandate it is therefore an illusion, and so it's not surprising at all that it isn't replacing C++.

skocznymroczny• 3 years 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

smcl2• 3 years ago

Is that available at compile time, though?

mhh__10• 3 years ago

Yes

alex_muscar3• 3 years 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• 3 years 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-...

2h• 3 years 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__10• 3 years 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...

btschaegg• 3 years ago

Also I physically shuddered when I saw the word template. Did no one learn from C++ mistakes?

While we might disagree on a lot of semantical things on this, I'd argue that D very much learned from those mistakes. There's a strong argument for D's templates to be "templates done right" (which C++'s most certainly aren't).

So I encourage you to read more into this topic. To me, this question seems just about as uninformed as someone complaining about a LISP tutorial on macros, asking "did no one learn from the mistake that is the C preprocessor?".

If/where there are other models better suited for metaprogramming would be another (interesting) discussion (full of tradeoffs, I'm sure), but the notion of proper (hygienic?) templates not being adequate anywhere can certainly not be inferred from C++'s implementation alone.

alex_muscar3• 3 years ago

That's right. The Cobol version has its own beauty because it's built into the language. Also, this is my TIL nugget of the day. Thanks :)

kazinator• 3 years ago

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

Kukumber3• 3 years 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• 3 years 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.

Kukumber3• 3 years 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

Beautiful Binary Search in D

Related Stories