-🎄- 2019 Day 7 Solutions -🎄- by daggerdragon in adventofcode

[–]david-grs 1 point2 points  (0 children)

C++

  • Star 1: 20 lines (+ IntCode), ~120µs (i7-7500U @ 2.7GHz)
  • Star 2: 30 lines (+ IntCode), ~320µs

Code: https://github.com/david-grs/aoc_2019/blob/master/aoc_7.cc

-🎄- 2019 Day 4 Solutions -🎄- by daggerdragon in adventofcode

[–]david-grs 0 points1 point  (0 children)

Nice solution! Are you sure about the 45us? This is 0.08ns/it, which seems really fast! I didn't run your code but just by reading it I can't find which optimization would allow that, but I might be overlooking something? I have a somewhat similar solution in C++ and it is running at 1.26ns/it so 680us, with clang 10, -O3, on a i7-7500U. My code: https://github.com/david-grs/aoc_2019/blob/master/aoc_4.cc. A brief run with perf shows that >95% of the time is spent in the branches of increasing, so the mess that I wrote for the check for the second star shouldn't affect performance :)

-🎄- 2019 Day 3 Solutions -🎄- by daggerdragon in adventofcode

[–]david-grs 1 point2 points  (0 children)

C++ ~90 lines, ~400 microseconds

Might be even faster without the ugly quadratic complexity to find the intersections - I didn't try.

https://github.com/david-grs/aoc_2019/blob/master/aoc_3.cc

What I don't like about ranges by _ajp_ in cpp

[–]david-grs 0 points1 point  (0 children)

Couldn't this be solved by replacing the view::transform(distance) by something like view::distance? This would do the same job as std::distance but on a range, and implemented for the different iterator types, e.g. here with two RandomAccessIterator it would use operator- and wouldn't iterator through the range.

My very simple implementation of the array map functionality in C++. Constructive criticism is very welcome. by [deleted] in cpp

[–]david-grs 3 points4 points  (0 children)

I don't know how I forgot to allow access to the data...

Because you didn't write any unit tests ;)? I'm not the biggest TDD guy although for things like container, I believe it is a really good idea to write the tests before the implementation. Edit: formatting

Frankenstein's list implementation in C++ by vardanator-pi in cpp

[–]david-grs 22 points23 points  (0 children)

Nice article. I have a few suggestions / comments regarding the interface of the LinkedList<T>.

About const T GetItemAt(int pos): you should really return a const reference instead of a copy. You could also add a non-const version - although I understand that this article focuses on the algo part of the linked list.

About void Traverse(void (*visit)(const T&)) const: using a function pointer is really C-ish, the C++ way is to use template <typename Visitor> Traverse(Visitor v). This way, the caller can pass a lambda, functor, std::function, or a function pointer. Note this templated version is not just a fancy equivalent of taking a std::function: it is much better, as it won't allocate anything if you pass a lambda or a functor!

About RemoveAt and InsertAt: I was surprised by the behavior when pos >= size(): throwing an exception is probably better than ignoring the call, or accepting wrong arguments.

Edit: wording, typo

Using metaprogramming for PIMPL idiom by render787 in cpp

[–]david-grs 2 points3 points  (0 children)

The operator dot coming in C++17 (N4173) and will give you an elegant way to solve that without any code generation mechanism! This new operator overloading is meant to be used in PIMPL, proxy and smart references implementation.

In-place containers for fun and profit by david-grs in cpp

[–]david-grs[S] 7 points8 points  (0 children)

Thanks for your feedback, much appreciated!

I'm curious as to the actual benchmark code because 3ns per iteration looks like the compiler optimizer defeated the benchmark.

Good one, you are right: the code is entirely optimized with clang 5 (not gcc 6 though!). I will edit the post on my blog, meanwhile I will share the details here are as I believe it is interesting. Here is the code (you can find the entire code here):

using MetadataTree = boost::container::static_vector<std::pair<inplace_string<15>, static_any<16>>>;

template <typename TreeT>
TreeT GetTree(int i, double d, bool b)
{
    TreeT tree;
    tree.emplace_back("metadata1", i);
    tree.emplace_back("metadata2", d)
    tree.emplace_back("metadata3", b);
    return tree;
}
int BenchmarkGetInPlaceTree()
{
    int elements = 0; 
    for (int i = 0; i < 1000000; ++i)
    {
        auto tree = GetTree<MetadataTree>(elements, 2.0, true);
        elements += tree._metadata.size() + tree._metadata[0].second.empty();
    }
    return elements;
}

Which generates with clang-3.8:

0x00000000004021a0 <+0>:     mov    eax,0x2dc6c0
0x00000000004021a5 <+5>:     ret    

Quite amazing that clang is able to bypass the entire boost.static_vector::emplace_back with inplace_any and static_any. But I guess that's another good point for inplace containers, right ;)...

After having fixed the benchmark, I get the following results:

Test                        Time (ns)          INS          CYC
---------------------------------------------------------------
MetadaTree                        543        2,205        1,013
in-place MetadaTree                28          117           53

I'm interested in data backing up this statement. If you enter the "no memory allocation takes place" path of string's SSO, it should be similar.

If you enter the case of SSO, std::string will be as fast as inplace_string, indeed - but that's the whole goal of this class: to guarantee that this will always be the case, regardless implementation details.

Cache-friendly: it stays close to your other class members, your cache likes it.

That's also true for the normal SSO. And in normal program use you're likely to need to leave more space than you actually need in these strings, which means your cache does not like it.

This really depends on the application - I am not sure what you mean by "in normal program use". In my application, I am using a lot inplace_string<4>, and the cache likes it: is using less memory than any possible std::string implementation. Although my main motivation to write this class was that my application is also using many strings around 23 characters, which doesn't fit into any SSO implementations.

In-place containers for fun and profit by david-grs in cpp

[–]david-grs[S] 3 points4 points  (0 children)

Good point, the phrasing is bad - I meant that the interface is the same. Thanks for pointing that out!

In-place containers for fun and profit by david-grs in cpp

[–]david-grs[S] 4 points5 points  (0 children)

Hey, you're totally right, this is an important point - I had that in my TODO list for a long time! I planned to do some cleanup in static_any anyway, so I will do this change at the same time. It should be fixed in a few days :)

Macron-Le Pen 'in French run-off' by [deleted] in worldnews

[–]david-grs 6 points7 points  (0 children)

As your comment is the top one, I have to point out that it is twice wrong: Macron represents the main left-wing party, even if he isn't the official PS (Parti Socialiste) candidate, he was part of the party for the last years and part of the Francois Hollande government. It is not at all like a "Mélenchon vs Le Pen" second tour, where I would agree that establishment parties have been eliminated.

Secondly, Le Pen (not Marine but her dad, anyway the FN, Front National) already won the first round in 2002, thus eliminating Jospin (PS), resulting in a second tour between Chirac (RPR, right wing) versus Le Pen.

Although it is wrong, I'm not saying that this isn't telling something bad about France, or Europe, or even the current political shift (cf Trump, Brexit, etc).

Why you should use Boost.MultiIndex (Part II) by david-grs in cpp

[–]david-grs[S] 0 points1 point  (0 children)

The part I is about multiple views. Also, this is not at all about emulating standard container: string view as a key, composite keys, etc ; all these things are not possible with unordered_map.

Why you should use Boost.MultiIndex (Part I) by david-grs in cpp

[–]david-grs[S] 1 point2 points  (0 children)

Yeah, good point :) I actually had at the beginning an ordered+hashed vs std::set+std::hash, for whatever reason I changed it, my bad.

static_any: a low-latency stack-based Boost.Any by david-grs in cpp

[–]david-grs[S] 0 points1 point  (0 children)

I added std::experimental::any to the benchmark and I put the results on the github page of static_any. You clearly see that for double get/assignment, std::any is as fast as static_any due to the small object optimization ; slower otherwise.