Блог пользователя nor

[C++] Avoiding temporaries — generalizing i++ using std::exchange
Автор nor, 13 месяцев назад, По-английски

https://nor-blog.codeberg.page/posts/2023-11-27-std-exchange-cpp/

  • Проголосовать: нравится
  • +235
  • Проголосовать: не нравится

»
13 месяцев назад, # |
← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

Great blog! Thank you so much. I wish I could upvote twice.

→ Ответить
  • »
    »
    13 месяцев назад, # ^ |
      Проголосовать: нравится +9 Проголосовать: не нравится

    Glad that you liked the blog. I'm planning to write some more C++ blogs too.

    → Ответить
»
13 месяцев назад, # |
  Проголосовать: нравится +32 Проголосовать: не нравится

I use it in non-recursive get in dsu

while(i != p[i]) i = exchange(p[i], v);

→ Ответить
»
13 месяцев назад, # |
  Проголосовать: нравится +11 Проголосовать: не нравится

Just want to put the function signature of std::exchange here. I think I understand better after I know its signature.

template< class T, class U = T >
constexpr T exchange( T& obj, U&& new_value );
→ Ответить
  • »
    »
    13 месяцев назад, # ^ |
    ← Rev. 2   Проголосовать: нравится +8 Проголосовать: не нравится

    Yeah, in retrospect it seems that I should have put it in the blog for people who know about templates.

    → Ответить
»
13 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

I think, copy_c_string should be implemented as while (*output++ = *input++); in order to terminate the copied string with '\0' in the output.

→ Ответить
  • »
    »
    13 месяцев назад, # ^ |
    ← Rev. 2   Проголосовать: нравится +8 Проголосовать: не нравится

    Yeah, my bad, somewhere I had switched from copying arrays to C strings. The example holds for both, and this one liner shows the true power of null-terminated strings (not that I would use null-terminated strings anywhere given that std::string exists). Updated the blog, since now the algorithm can be used to concatenate multiple strings.

    → Ответить
»
13 месяцев назад, # |
← Rev. 2   Проголосовать: нравится +11 Проголосовать: не нравится

We can also use std::tie(a, b) = std::make_pair(b, a + b) Similar to python, very readable.

→ Ответить
  • »
    »
    13 месяцев назад, # ^ |
      Проголосовать: нравится +13 Проголосовать: не нравится

    The only problem with this piece of code is too many copies, std::exchange is faster on larger structs. Definitely more readable though, to the extent that I had used this as an explanation for the functionality of std::exchange.

    → Ответить
»
13 месяцев назад, # |
  Проголосовать: нравится +16 Проголосовать: не нравится

From this blog post, I learned that extended gcd can be implemented non-recursively (or at least with no backtracking).

→ Ответить
  • »
    »
    13 месяцев назад, # ^ |
      Проголосовать: нравится +28 Проголосовать: не нравится

    I found it a bit surprising that most people implement extended GCD recursively, given that recursion is not very obvious (at least to me), and each step of extended GCD is just manipulating coefficients so that the equation is true before and after the operations that replace arguments with their new values.

    → Ответить
    • »
      »
      »
      13 месяцев назад, # ^ |
        Проголосовать: нравится +39 Проголосовать: не нравится

      I think it's just because it was done recursively on emaxx, and from then on we do it exactly that way.

      → Ответить
»
13 месяцев назад, # |
  Проголосовать: нравится +17 Проголосовать: не нравится

An important thing to keep in mind is that most things in your code aren't bottlenecking the performance, and this gets more true the more complex your code gets, so how exactly you write them (as opposed to what logic you implement) is almost irrelevant. You shouldn't overoptimise or worry about maximum performance ahead of time. Just write something that's not slow (good algorithm and follow basic patterns like processing inner array in inner loop), check if it's good enough and move on. Your writing time is more valuable than the resulting program's time.

It's useful to know these things just in case you find out that your code isn't good enough and you need hardcore optimisations, or if you're writing a performance-critical library that's going to be reused.

→ Ответить
  • »
    »
    13 месяцев назад, # ^ |
    ← Rev. 3   Проголосовать: нравится +9 Проголосовать: не нравится

    I'm not sure where performance comes into discussion here. That is unless it is an argument for using i++ instead of ++i, targeted towards people who use ++i because of performance claims, which have been debunked in the blog too, except for the cases where the operators are defined for a class and can have potentially different behaviour.

    Also, I believe that when writing code, readability becomes quite important as the code becomes more and more complex. So expressing intent through code properly can prevent you from having bugs in the first place as well as help you catch bugs.

    If you're referring to the topic of the blog and didn't bother reading the content, it was more about getting rid of temporaries because they make code uglier, rather than performance considerations, since the compiler will generate the same code most of the time.

    → Ответить
    • »
      »
      »
      13 месяцев назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Yeah, I was referring to those performance claims you addressed at the start — even if they were true, it almost doesn't matter.

      Regarding readability of code, it's not all that much about exact implementation, since the definition void copy_c_string(const char* input, char* output) offers much more info about what that code is supposed to do than the function body itself. When the code is structured like this, implementation of individual building blocks will need to be read less, and the most readable code is one where you don't need to look into extra details at all.

      → Ответить
      • »
        »
        »
        »
        13 месяцев назад, # ^ |
        ← Rev. 3   Проголосовать: нравится +3 Проголосовать: не нравится

        Ah, that makes more sense.

        Regarding whether it is important to implement it properly — well, if it is write-once read-never code, then it makes sense to only have good names (and short functions like this) and not care about quality of implementation so much as long as it just works. Maybe this was not a very good example given how short it was, but in both longer functions (complicated functionality) as well as code that needs to be maintained (for example, during refactoring), having a harder-to-modify-incorrectly implementation is more preferable in general — in fact this is why functional code is seen as cleaner.

        This might only be partially true for competitive programming, where we optimize for writing once and not for maintaining, but is something that should be kept in mind in general.

        → Ответить
»
13 месяцев назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

Some other examples taken from code I wrote in the past

// union-find path compression
int find(int i) {
  int j = i;
  while (j != rep[j]) j = rep[j];
  while (i != j) i = exchange(rep[i], j);
  return j;
}

// delete a linked list
void del(list* p) {
  while (p) {
    delete exchange(p, p->next);
  }
}

// print space-separated ints
void print(vector<int> v) {
  auto sep = "";
  for (int x : v) {
    cout << exchange(sep, " ") << x;
  }
→ Ответить