Ivan Krivyakov https://ikriv.com/blog Premature optimization is the root of all evil Thu, 29 Feb 2024 00:40:20 +0000 en-US hourly 1 https://wordpress.org/?v=6.4.3 Logarithmic Fibonacci https://ikriv.com/blog/?p=4947 https://ikriv.com/blog/?p=4947#respond Thu, 29 Feb 2024 00:40:20 +0000 https://ikriv.com/blog/?p=4947 […]]]> Code: https://github.com/ikriv-samples/logarthmic-fibonacci.

Fibonacci sequence is defined as a sequence starting with 0, 1 where each subsequent member is calculated as fib(n) = fib(n-1)+fib(n-2). This yields an infinite sequence 0, 1, 1, 2, 3, 5, 8, 13, …

This repository compares several approaches to calculating nth Fibonacci number:

  • A naïve recursive solution
  • A simple linear solution
  • A solution that runs in logarithmic time

Running The Samples

python main.py {algorithm} n 

Algorithm can be one of linearrecursive, or logarithmic. If the algorithm is omitted, logarthmic is used.

Naïve Solution

It is very easy to program Fibonacci sequence exactly as defined, but it leads to a slow and inefficient solution:

def fib(n: int) -> int:
    if n==0: return 0
    if n==1: return 1
    return fib(n-1)+fib(n-2)

This solution has exponential runtime, so it hits extremely long calculation times for relatively small values of n. On my machine python main.py recursive 40 takes over 20 seconds.

Linear Solution

def fib(n: int) -> int:
    if n==0: return 0
    if n==1: return 1
    prev,current=0,1
    for i in range(n-1):
       prev,current=current,prev+current
    return current

This solution works well up to n=100,000 or so, but then it starts to lag.

Logarithmic Solution

This solution is based on the fact that 2×2 matrix

    | 1    1 |
A = |        |
    | 1    0 |

when raised to the power of n yields

        | fib(n+1) fib(n)   |
A**n == |                   |
        | fib(n)   fib(n-1) |

Proof

The above property can be proved by induction. It is obviously true for n=1. Now, supposed it is true for n=k, so

        | fib(k+1) fib(k)   |
A**k == |                   |
        | fib(k)   fib(k-1) |

Then A**(k+1) is (A**k)*A, or

           | fib(k+1) fib(k)   |   | 1   1 |    | fib(k+1)+fib(k)    fib(k+1) |
A**(k+1) = |                   | * |       | == |                             |
           | fib(k)   fib(k-1) |   | 1   0 |    | fib(k)+fib(k-1)    fib(k)   |

Simplifying this, we get

           | fib(k+2)  fib(k+1) |
A**(k+1) = |                    |
           |  fib(k+1)  fib(k)  |

So, the property is proved by induction.

OK, we proved it. So?

We can exploit the fact that matrix multiplication is associative to make the number of computations logarithmic. If n is a power of 2, we can compute A**n in log2(n) steps. For example, if n=16, we can compute it in 4 steps:

A2=A*A
A4=A2*A2
A8=A4*A4
A16=A8*A8

If n is not a power of 2, we will assemble A**n from parts using binary representation of n:

n = 11 == 1011b
A2=A*A
A4=A2*A2
A8=A4*A4
An=A*A2*A8

We can build the result gradually, there is no need to keep the intermediate values:

result=A
A2=A*A
result=result*A2
A4=A2*A2
A8=A4*A4
result=result*A8

The same code in Python:

def power(m: Matrix, n: int) -> Matrix:
    result=Matrix(1,0,0,1)
    currentPower=m
    while n>0:
        if n%2==1:
            result=result*currentPower
        n=n//2
        if n>0:
            currentPower=currentPower*currentPower
    return result

def fib(n: int) -> int:
    if n==0: return 0
    return power(Matrix(1,1,1,0), n-1)[0]

The complete code is in logarithmic.py

Execution Times

Recursive approaches runtime increases exponentially. It becomes over 20 seconds for n=40. Linear approach works well up to n~=100,000. Logarithmic approach can calculate value of fib(10_000_000) in a few seconds. We must remember that logarithmic approach is logarithmic only in terms of the number of Python integer multiplications. Since Python integers have arbitrary length, multiplications get slower and slower as the numbers become bigger, so the actual wall clock times will not be truly logarithmic.

]]>
https://ikriv.com/blog/?feed=rss2&p=4947 0
Running Pytorch with Apache mod_wsgi https://ikriv.com/blog/?p=4938 https://ikriv.com/blog/?p=4938#respond Sun, 25 Feb 2024 07:14:58 +0000 https://ikriv.com/blog/?p=4938 […]]]> TL;DR make sure to add magic words WSGIApplicationGroup %{GLOBAL} to the Apache config, otherwise import torch will hang.

I tried to integrate my PyTorch AI model with my Apache web site, so I could play with it interactively. I chose to use raw WSGI script, since I did not want to invest in creating a full-blown Django or Flask solution. By the way, here’s a tutorial on how to inregrate Pytorch with Flask.

The ‘hello-world’ WSGI script worked, but importing torch caused WSGI process to hang, with eventual “gateway timeout” returned to client.

After a few hours, I found the reason. WSGI uses Python sub-interpreter by default, and apparently PyTorch cannot run in a sub-inerpeter. To prevent WSGI from using a sub-interpreter, it should run in daemon mode as part of “global group”. The working version of my Apache virtual host config contains the following WSGI-related directives:

WSGIScriptAlias /api/wsgi /var/www/mysite/api/wsgi.py
WSGIDaemonProcess mysite processes=2 threads=5 display-name=ivk-wsgi
WSGIApplicationGroup %{GLOBAL}

Additional notes:

  • WSGI process still shows up as ‘apache2’ when listing processes via ps -A. It shows up as ‘ivk-wsgi’ when using ps -ax.
  • WSGI process cannot run as root, it runs as www-data.
  • In a docker container, gdb by default refuses to attach to other user’s processes, even if you are root.
  • To overcome that, use --privileged switch as follows: docker exec --privileged -it container bash

The problem with hanging torch will affect any WSGI server, including Django and Flask, as evidenced by this StackOverflow:
https://stackoverflow.com/questions/62788479/how-to-use-pytorch-in-flask-and-run-it-on-wsgi-mod-for-apache2.

So, even if I went ahead with the Flask tutorial, I would have faced the same problem, with more moving parts to debug.

PS. Maybe I should have listened to the advice to use gunicorn instead of mod_wsgi, but using modules seemed cleaner, and “gunicorn” also has problematic pronunciation issues. Do you render it as “gunny corn”, “goony corn”, or “gee unicorn” (answer)? Anyway, I ended up using mod_wsgi.

]]>
https://ikriv.com/blog/?feed=rss2&p=4938 0
Ubuntu: uid/gid option required to gain write access to remote share https://ikriv.com/blog/?p=4936 https://ikriv.com/blog/?p=4936#respond Fri, 23 Feb 2024 16:28:51 +0000 https://ikriv.com/blog/?p=4936 […]]]> I have Synology NAS, and I share the “home” directory as a CIFS share.

From Windows, I simply do net use N: \\home\nas /user:myuser *, and it works.

Corresponding command from Ubuntu is

sudo mount -t cifs //nas/home /mnt/nas -o username=myuser

It works, but the mount is effectively read-only: I am unable to make any modification to remote files or create new files/directories. The effect is the same even if I add “rw” option.

I used ChatGPT to ask what to do in this case, and it advised to add “uid” and “gid” parameters. Apparently, remote files are considered to be owned by ‘root’, and my users is not allowed to make changes. The following command works:

sudo mount -t cifs //nas/home /mnt/nas -o username=ikriv,rw,uid=1000,gid=1000

Here “1000” is ID of the user root. I suppose “rw” is redundant, but it does not harm.

]]>
https://ikriv.com/blog/?feed=rss2&p=4936 0
WordPress themes and software decay https://ikriv.com/blog/?p=4927 https://ikriv.com/blog/?p=4927#respond Wed, 14 Feb 2024 00:58:49 +0000 https://ikriv.com/blog/?p=4927 […]]]> I have discovered a few broken things with my WordPress site. This post, as much of this blog, is mostly description of events, so I won’t forget what exactly happened. To avoid boring details, feel free to read the summary and jump to “conclusions” at the end.

  • My theme “rotted” over time: the “menu” button stopped showing on mobile and on smaller windows on desktop.
  • Changing/upgrading theme caused a critical error, permanently disabling the web site.
  • I had a really hard time finding a suitable theme.

I haven’t touched WordPress configuration for several years, I was just doing ordinary upgrades. At some point, it fell victim of software rot.

Escape from WordPress: enter Ghost

All of the above was frustrating enough that I made an attempt to escape from WordPress and try a different blogging platform. Various forums recommended Ghost, so I created a Ghost droplet on Digital Ocean and gave it a go. First thing, it lied to me about my email: it said it would only be needed for an SSL certificate, but then I received an email titled “Your New Ghost Site” and signed “Team Ghost”. Not cool.

More importantly, I was not able to transfer my blog content to Ghost. I installed their export plugin, and it created a zipped file, which contained some JSON. It didn’t contain the uploaded media as it should have, but whatever, I was ready to move the media manually. Anyway, any attempt to import the file into Ghost resulted in an error box sayin “, cannot fetch db“. Yes, it started with a comma. I tried the same with raw JSON, but no success. Other people reported the same error (https://forum.ghost.org/t/migrating-from-wordpress-not-working/44422/7), but I was unable to find a fix. So, back to WordPress I went.

Can’t Change Themes

Attempt to change theme made mye site permanently unusable. Investigation showed that it is related to the content of the database. The $sitebars_widgets map contained a key that is mapped to NULL:

(
    [wp_inactive_widgets] => Array(...)
    [primary] => Array(...)
    [subsidiary] => NULL
)

This causes an exception when WordPress tries to merge all values into one big array. The site then becomes permanently unusable, it is not possible to change the theme back via the GUI, the only way to do it is to restore the original database from backup.

The actual exception text is in Apache log.

Fatal error: Uncaught Error: array_merge(): Argument #3 must be of type array, null given in wp-includes/widgets.php on line 1342

This problem was reported by multiple people: https://core.trac.wordpress.org/ticket/57469. Since $sitebar_widgets is a global variable, it is difficult to tell how exactly it is set. The problem can be fixed by adding the following code to retrieve_widgets() in wp-incudes/widgets.php just before the call to _wp_remove_unregistered_widgets():

// remove any NULL elements
$sidebars_widgets = array_filter($sidebars_widgets);

It suffices to change theme once with this code present, after which the database is fixed, and the patch can be removed.

Once I was able to change themes again, I was hoping to find a new theme I can switch to.

Choosing a New Theme

There are literally thousands of themes for WordPress, and it is not easy to find a good one.

  • Most theme previews are dominated by cover image, which does reflect actual look of the theme.
  • Most themes show posts in multiple columns and/or limit the screen width.
  • Many themes are broken in interesting ways: e.g. they can’t display site logo, title, and tagline at the same time, or they don’t support sidebars, etc.
  • Lots of themes contain unnecessary repetitive elements, like giant red “CONTINUE READING” button after every post header.
  • Many themes refer to some additional “builder” plugins.
  • Lots of themes are commercial, i.e. extra features need to be unlocked for a fee. This is alright, but there is no way to filter for actually free themes.
  • Many themes introduced changes to global styles of element such as <li> or <a>, which broke other pages on my web site.

Out of thousands of themes available, it proved to be impossible to find a theme that answers to my rather simple requirements:

  • Continuous flow of blog posts, no multi-column.
  • No artificial width restrictions.
  • Site logo, name, and tagline all displayed on top.
  • Sidebar support.
  • Mobile support.
  • No atrocious repeatable elements such as “learn more” or “press here to continue” after every post.
  • Ability to customize colors.

I am sure such theme exists, but I was not able to find it. A few themes came close to what I needed: Asteroid, Blogstream, Zarka. However, the amount of work needed to get them to look “right” seemed to be greater than fixing my old theme.

Living on an old Theme

My current theme is Stargazer, which I selected a few years ago. Stargazer theme was created by Justin Tadlock (https://justintadlock.com/), with the latest version dating back to 2018 (https://github.com/justintadlock/stargazer).

I invested quite a few hours into customizing it via a child theme, so it looked like I wanted. The customization involved touching a number of theme specific styles, and even modifying small pieces of PHP code. All customizations live in “stargazer_child” folder, so they could be re-applied when the main theme is upgraded.

Stargazer worked great for me, but at some point handling of the “hamburger” menu got broken.

No menu button

I have “secondary menu” on my blog page (“Articles”, “Code”, …) that is supposed to collapse into a “hamburger” button on smaller screens.

It used to work when I adopted the “Stargazer” theme a few years ago, but not anymore. The culprit turned out to be “screen-reader-text” style, which makes objects invisible. So, the menu was there, but it was not displayed.

With some amount of patience and with great help from Chrome developer tools, I was able to update my child theme to fix the problem and make the menu look exactly like I wanted. I am a little concerned about running a 8 year old theme, but I guess if it works, don’t fix it.

Conclusion

All software, including WordPress themes, decays over time, unless it operates in a completely self-contained jar. Protocols change, things get moved around, external services come and go, minor details get updated quietly. So, having a few things broken after 8 years is expected.

What was not expected is (a) fragility of WordPress, and (b) difficulty of finding a decent theme that answers to my taste.

I was unable to rescue my side without diving rather deep into WordPress code and debugging PHP. I haven’t done anything outrageous. The error message displayed is rather generic and gives zero direction on what to do. It does not even say how to find the actual exception text. I can only imagine how scary it must be for non-technical WordPress users who don’t know how to code.

I was also unable to find a “good” theme out of several thousand available on WordPress web site. Generally, finding a theme was a rather frustrating and slow experience. Fixing my 8 year old theme proved to be easier than customizing a new theme. I’d say this is rather sad state of affairs.

]]>
https://ikriv.com/blog/?feed=rss2&p=4927 0
C++ how future::wait_until(time) handles multiple clocks? https://ikriv.com/blog/?p=4923 https://ikriv.com/blog/?p=4923#respond Thu, 04 Jan 2024 16:24:13 +0000 https://ikriv.com/blog/?p=4923 TL;DR

std::future::wait_until(time) converts time to a standard clock, and thus implicitly assumes that all clocks run at the same pace.

More Details

I was writing unit tests for various retry scenarios, such as “try again after a minute”. With naïve approach, it would lead to very long running tests, which is a no-no. To avoid the waits, I abstracted access to the clock in the code, so I could “control time”. It worked great for the most part, but future::wait_until() refused to cooperate and gave me timeouts.

This made me wonder: how future::wait_until() handles multiple clocks in the first place?

C++ provides two standard clock types: system_clock, which is tied to an actual calendar time and steady_clock, which is guaranteed to never jump back and forth, but cannot be easily converted to calendar time. In practice it is usually the time since the machine boot. In theory, it should be possible to have user-defined clock types as well.

So, how future::wait_until() could handle a custom clock type? The answer is somewhat disappointing, but not surprising. Both GCC and MSVC implementations convert custom clock to a standard clock, and use that standard clock to wait. GCC uses vanilla std::chrono::system_clock, MSVC uses “xtime“, which is time in nanoseconds from some epoch. Coming to think of it, this is probably the only reasonable solution, since “clock” interface does not provide a wait facility.

This means that wait_until assumes that all clocks move at the same pace, which may not be true in the pretend world of unit tests.

The good news is that if the future is already satisfied, i.e. the result is already available, wait_until will ignore the time parameter, and will return immediately. So, it would work even if you pass it some weird time a few hundred years in the past.

So, the solution would be to either abstract the wait interface and avoid calling wait_until directly, or ensure that all futures are satisfied and wait_until is a no-op.

]]>
https://ikriv.com/blog/?feed=rss2&p=4923 0
Design and evolution of C++ future continuations https://ikriv.com/blog/?p=4916 https://ikriv.com/blog/?p=4916#respond Tue, 02 Jan 2024 02:48:36 +0000 https://ikriv.com/blog/?p=4916 TL;DR: C++ futures lack continuation

“Continuation” is a rather standard concept in concurrent programming. JavaScript has promise.then, .NET has Task.ContinueWith. I was somewhat surprised that standard C++ std::future has no concept of “continuation” as of C++ 23.

  • Boost version sort of has it, but only if you turn on an undocumented #define.
  • It has been “experimental” for 11+ years, but not for lack of trying.
  • Multiple proposals were put forward, withdrawn, and re-proposed, but none has been accepted as of C++ 23. The earliest it can appear is C++ 26, but that’s not certain. I don’t want to be judgmental here, but the word “dysfunctional” is not leaving my mind.

But what about coroutines?

It’s a very good question. Coroutines (co_await/co_return) are by definition continuations, so they solve this problem, but in a completely different plane. Any code that uses futures would have to undergo significant rewrite to use co-routines. This may be a subject of another post.

std::future

Standard std::future does not have a then method, and never had. So, if I have a function returning a future, there is no way to say “call this other function returning a future, and when it’s done, do something else”.

future<string> get_text() {...}

class Parser {
   promise<MyData> m_promise;

   MyData parse_test_to_data() { ... };
public:

   future<MyData> get_parsed_data() {
    // obtain raw text, then parse it into data
    return get_text().then( // NOT AVAILABLE IN STANDARD C++!
       [this](const string& text) { m_promise.set_value(parse_text_to_data(text)); 
    }
}

Furthermore, std::future<T> is not convertible to future of any other type:

  • std::future<T> is not convertible to std::future<void>
  • std::future<TDerived> is not convertible to std::future<TBase>
  • std::future<short> is not convertible to std::future<int>

The reason for this is related: it would be trivial to implement via “wait, and then convert”, but std::future has no “then” facility.

boost::future::then

This method exists in a semi-zombie state:

  • It was added as “experimental” in 2012.
  • It is not included in the default code body of the library.
  • It is hidden behind an undocumented #define BOOST_THREAD_PROVIDES_FUTURE_CONTINUATION.
  • Boost documentation marks it as “extension” and adds a no-nonsense warning:
    These functions are experimental and subject to change in future versions. There are not too much tests yet, so it is possible that you can find out some trivial bugs 🙁

The #define part makes using the method especially problematic. If my code lives in a library, I cannot frivolously turn on arbitrary #defines, unless the entire ecosystem has agreed on it. Otherwise, my code and the client code would effectively use different flavors of boost, and the best I can hope for is quick and painless death by segmentation fault. This makes configuring header-only libraries via defines problematic in general, but it’s a subject for another post.

The road to hell is paved with good proposals

P0159, Concurrency TS Proposal: 2015-2019

The “concurrency TS” proposal, that would add future::then to the C++ standard was put forward in October 2015: P0159r0. It was probably not the first one, but anyhow, it was over 8 years ago. That proposals had been considered for over 3 years, only to see the std::future being withdrawn in January 2019 in favor of a “Facebook effort”. I suppose this has something to do with the Folly library, perhaps specifically Folly executors, but that’s not certain.

P0443, C++ Executors Proposal: 2016-2021

Eric Niebler, one of the authors of the “concurrency TS” explains why future::then is a bad idea in his CppCon 2019 talk. Thus, the “concurrency TS” proposal was rejected in favor of the “C++ executors proposal”, known as P0443. It was first put forward in October 2016 as P0443r0, with the last revision P0443r14 made in September 2020. Throughout 2021, there discussions about a “one grand unified model for asynchronous execution“, which resulted in the abandonment of P0443 in favor of P2300, the std::execution proposal.

This proposal calls for a free-standing then function that supersedes future::then and accepts a sender and a receiver.

P2300, std::execution proposal: 2021-present

This proposal was put forward in June 2021 as P2300r0 and underwent several revisions, the last one at the time of writing being P2300r7 from April 2023. It is based on P0443, but has significant design changes. Section 1.9, “Design changes from P0443″ states that “the executor concept has been removed and all of its proposed functionality is now based on schedulers and senders, as per SG1 direction“.

However, global then function remains virtually unchanged, see section 1.5.1.

P2300 did not make it into the C++23 standard. It might go into C++26, or it might not, if the C++ committee decides to make further refinements or to change the direction yet again.

Folly

Meta’s Folly library has its own nomenclature of concurrency-related facilities. It provides continuations via Future::thenValue method. Folly documentation gives the following example:

  folly::ThreadedExecutor executor;
  cout << "making Promise" << endl;
  Promise<int> p;
  Future<int> f = p.getSemiFuture().via(&executor);
  auto f2 = move(f).thenValue(foo);
  cout << "Future chain made" << endl;

Conclusion

Standard C++ is still lacking standardized future continuation. Boost has “experimental” implementation that is 11 years old. In the meantime, at least three major proposals were brought before the standard committee, but none made it into the standard. Current proposal is 190 printed pages long. The earliest it can become standard is C++26, and even that is not guaranteed. Such glacial speed of change results in a lot of confusion and feature lag behind other languages. C# had continuations since 2010, and JavaScript since 2015 (EC6). While C++ 11 was relatively on par with the industry when introducing futures, current C++ is quite behind the crowd. “Experimental”  code should not stick around for over a decade in any library, and especially in a semi-standard library like Boost. There must be a way to solve problems faster.

]]>
https://ikriv.com/blog/?feed=rss2&p=4916 0
C++ syntax rant (template guides) https://ikriv.com/blog/?p=4908 https://ikriv.com/blog/?p=4908#respond Wed, 04 Oct 2023 16:19:12 +0000 https://ikriv.com/blog/?p=4908 […]]]> C++ syntax is notoriously complex and full of gotchas both for compilers and for humans. I don’t know what was the reasoning in selecting the syntax for template deduction guides (C++ 17),  but it is outright confusing, in my humble opinion. Check it out:

// this is a deduction guide
template <std::integral T>
MyClass(T) -> MyClass<IntTag, T>;

// this is a function declaration
template<class T>
auto myClass(T) -> MyClass<IntTag,T>;

I mean, what was wrong with having something like template guide <std::integral T>? Yes, you would need a new (contextual) keyword, but at least it would be readable. I am sure the standard committee had very deep sounding reasons to choose the syntax they chose, but the result is not very readable to be honest.

UPDATE

I asked this question during a great talk about deduction guides given by Nina Ranns at CppCon 2023. The similarity between the function declaration syntax and deduction guide syntax is not coincidental. Internally, class template argument deduction is based on function template argument deduction, it builds a set of “notional functions” from the class constructor signatures, and deduction guides put additional “pseudo functions” into that set. This is my very rough understanding, which may not be entirely correct.

But these are implementation details, which did not have to leak into the syntax. According to Nina, alternative syntaxes were not carefully considered, the focus was on getting the guides to work.

This is understandable, but in the great scheme of things it added yet another element of confusion into already complicated C++ syntax where it is not always clear what is what. I believe we would be better off if template deduction guides had a clear indicator like template guide <std::integral T>...

]]>
https://ikriv.com/blog/?feed=rss2&p=4908 0
Stopping bash script on error, and what can possibly go wrong https://ikriv.com/blog/?p=4903 https://ikriv.com/blog/?p=4903#comments Fri, 22 Sep 2023 05:55:22 +0000 https://ikriv.com/blog/?p=4903 […]]]> TL;DR Don’t mix set -e and && operators in bash, it’s not going to work well.

What is ‘set -e’

Bash command set -e stops the script when any of the script commands fails. Or something like that, the big hairy devil is in the details. Suppose we want to download, build, test, and deploy some code using a bash script. We want to stop the entire script immediately if any of the steps fails. This is not something bash would do by default. We can combine all the steps using the && operator, but in real life it becomes really annoying really quickly, especially for large scripts with long winded commands:

#!/bin/bash
download &&
do_build &&
do_test &&
deploy

Alternatively, we can put set -e in the beginning of the script, and leave the rest as is:

#!/bin/bash
set -e
download
do_build
do_test
deploy

‘set -e’ does not mix well with &&

set -e comes with quite a few strings attached: in particular, it will stop only for “simple” commands. See this Stack Overflow question for more details.

Suppose ‘do_build’ fails in the following script:

#!/bin/bash
set -e
download 
do_build && do_test
deploy

Will the script stop? No! It will skip the ‘do_test’ command and go strait ahead to ‘deploy’. If ‘deploy’ manages to succeed, the whole script succeeds, even though we just failed the build and skipped the test. How do I know? The hard way. Our CI build failed in a similar manner, but overall result was “green”.

This is not a bug, this is a feature. do_build && do_test is not a simple command, so set -e treats it differently.

false && false and false && true will NOT stop the script.

On the other hand, false on its own, as well as false || false and true && false WILL stop the script.

Of course, if you read the documentation carefully, it all has an explanation, but the bottom line is very simple: do not mix driving and alcohol set -e and operator &&. Choose either one or the other, but not both.

]]>
https://ikriv.com/blog/?feed=rss2&p=4903 1
Fun with fold expressions https://ikriv.com/blog/?p=4890 https://ikriv.com/blog/?p=4890#respond Mon, 18 Sep 2023 05:25:43 +0000 https://ikriv.com/blog/?p=4890 […]]]> Fold expressions, starting with C++ 17, provide succinct, if somewhat unorthodox, syntax for processing of parameter packs.

Printing a pack to standard output

Suppose, I want to write a function that outputs a bunch of values to cout.

I can do something like this:

#include <iostream>
#include <sstream>

using namespace std;

class Printable {};

ostream& operator<<(ostream& s, Printable const&) {
    return s << "(I am a Printable)";
}
// end common preamble, all subsequent examples omit it

template <typename... Args>
void output_cout(Args&&... args) {
   (cout << ... << args); // binary fold expression; parentheses are mandatory
   // the above line is equivalent to cout << arg1 << arg2 << ... << argN;
}

int main()
{
    output_cout(1, "ab", 3.14, Printable()); // 1ab3.14(I am a Printable)
}

This prints all parameters to cout, glued together without spaces. This example uses a feature known as “binary fold expression”.

Printing a pack to the first parameter

We can make it more flexible, and shorter, if we assume that the first parameter of the pack is the destination, which can be of any type. This examples and all subsequent ones omit the common preamble seen in lines 1-11 of the first example.

template <typename... Args>
void output(Args&&... args) {
   (... << args); // unary fold expression; parentheses are mandatory
   // the line above is equivalent to arg1 << arg2 << ... << argN;
}

int main()
{
    output(cout, 1, "ab", 3.14, Printable()); // 1ab3.14(I am a Printable)
}

Adding spaces

In previous examples all values were glued together. What if we want to add a space between values? If we are OK with a trailing space, we can use a variant of the first example with a more sophisticated fold expression:

template <typename... Args>
void output_cout(Args&&... args) {
   (..., (cout << args << ' ')); // all parentheses are mandatory
   // the above line is equivalent to (cout << arg1 << ' '), (cout << arg2 << ' '), ..., (cout << argN << ' ');
}

int main()
{
    output_cout(1, "ab", 3.14, Printable());
    cout << '$'; // 1 ab 3.14 (I am a Printable) $
}

Here we use a unary fold expression with operator comma, and the inner expression contains two operators <<. We verify that we have an extra space in the end by adding a $ sign.

Getting rid of the final space

To get rid of the final space, we’d need to treat the last argument differently. This is not something fold expressions can easily do. One way to handle it is to avoid fold expressions altogether and switch to recursion insead:

template <typename THead, typename... TTail>
void output_cout(THead&& head, TTail&&... tail) {
    cout << head;
    // 'constexpr' below is very important, or the compiler will be looking for an overload of output_cout() without parameters   
    if constexpr (sizeof...(tail) > 0) { 
        cout << ' ';
        output_cout(tail...);
    }
}

int main()
{
    output_cout(1, "ab", 3.14, Printable());
    cout << '$';  // 1 ab 3.14 (I am a Printable)$
}

We can see that the final space is gone now.

Getting rid of the final space, fold expression style

Fold expressions insist on treating each argument identically, but we still can use them if we keep the state somewhere else.

class Joiner {
    bool _has_content;
public:
    Joiner() : _has_content(false) {}
    
    template<typename T>
    Joiner& operator << (T&& value) {
        if (_has_content) {
            cout << ' ';
        }
        cout << value;
        _has_content = true;
        return *this;
    }
};

template <typename... Args>
void output_cout(Args... args) {
   (Joiner() << ... << args); // binary fold expression
   // the above line is equivalent to Joiner() << arg1 << arg2 << ... << argN;
}

int main()
{
    output_cout(1, "ab", 3.0, Printable()); 
    cout << "$"; // 1 ab 3 (I am a Printable)$
    return 0;
}

Execution order

Placement of the ellipsis inside a fold expression changes the order in which operations are applied. If the operation is associative like operator comma, it does not matter, but for not associative operations like operator << or operator / it may change the result dramatically. We say that comma is associative, because (a,b),c is the same as a,(b,c). We say that division is not associative, because (a/b)/c is not the same as a/(b/c).

Consider this example:

template <typename... Args>
auto bigDivideLeft(Args... args) {
    return (.../args); // applies division left-to-right
}

template <typename... Args>
auto bigDivideRight(Args... args) {
    return (args/...); // applies division right-to-left
}

int main()
{
    cout << bigDivideLeft(1, 2.0, 4) << endl;  // 0.125 == (1/2.0)/4
    cout << bigDivideRight(1, 2.0, 4) << endl; // 2 == 1/(2.0/4)
    return 0;
}

bigDivideLeft() applies the division operator left to right, to it first divides 1 by 2.0, and then divides the result by 4. This is how division normally works in C++.

bigDivideRight() works in the opposite direction, it first divides 2.0 by 4, yielding 0.5, and then divides 1 by 0.5, yielding 2.

We can have binary fold expression variants of these two:

template <typename... Args>
auto bigDivideLeft(Args... args) {
    return (1.0/.../args); // applies division left-to-right
}

template <typename... Args>
auto bigDivideRight(Args... args) {
    return (args/.../4.0); // applies division right-to-left
}

int main()
{
    cout << bigDivideLeft(2, 4) << endl;  // 0.125 == (1.0/2)/4
    cout << bigDivideRight(1, 2) << endl; // 2 == 1/(2/4.0)
    return 0;
}

In our previous examples, (..., (cout << args << ' ')); can be replaced with ((cout << args << ' '), ...);, because comma is associative.

However, if we try to replace (... << args); with (args << ...);, we get a compilation error, because the execution of the operations starts from the right, and 3.14 << Printable() is not legal.

Conclusion

Fold expressions are a powerful tool, but they come with a cost.

Usability:

  • The syntax is succinct, but not very intuitive. Perhaps some kind of loop construct would be more helpful.
  • Parentheses are mandatory. If you forget parentheses, the whole thing is not recognized as a fold expression, and weird errors arise.
  • Different placement of ellipsis may yield different results if the operation is not associative.

Functionality:

  • Fold expressions will treat all arguments identically.
  • If we don’t want to treat the arguments identically, we must either avoid fold expressions, or introduce mutable state.

 

]]>
https://ikriv.com/blog/?feed=rss2&p=4890 0
C++: std::optional and std::variant will copy values by default https://ikriv.com/blog/?p=4882 https://ikriv.com/blog/?p=4882#respond Tue, 05 Sep 2023 14:24:22 +0000 https://ikriv.com/blog/?p=4882 […]]]> std::optional and std::variant are attractive alternatives to raw pointers and unions, but they come with a caveat: when you create an optional/variant from a “real” value, a copy will be created. To avoid that, one must use reference_wrapper, and of course be careful not to end up with a dangling reference.

The following code demonstrates that copying occurs when a value is passed to a function accepting a variant:

#include <iostream>
#include <variant>

using namespace std;

struct Foo {
    Foo() { cout << "Foo constructed" << endl; }
    Foo(Foo const& other) { cout << "Foo copied" << endl; }
    ~Foo() { cout << "Foo destroyed" << endl; }
};

struct Bar {
    Bar() { cout << "Bar constructed" << endl; }
    Bar(Bar const& other) { cout << "Bar copied" << endl; }
    ~Bar() { cout << "Bar destroyed" << endl; }
};

void f(variant<Foo,Bar> foobar) {
    auto const* text = holds_alternative<Foo>(foobar) 
        ? "Foo" 
        : (holds_alternative<Bar>(foobar) 
            ? "Bar" 
            : "unknown");
    cout << "f(" << text << ")" << endl;
}

int main()
{
    f(Foo{});
    f(Bar{});

    return 0;
}

Output:

Foo constructed
Foo copied
f(Foo)
Foo destroyed
Foo destroyed
Bar constructed
Bar copied
f(Bar)
Bar destroyed
Bar destroyed

To avoid copying, one must use a reference_wrapper. Note that it is now impossible to pass a temporary:

#include <iostream>
#include <variant>
#include <functional>

using namespace std;

struct Foo {
    Foo() { cout << "Foo constructed" << endl; }
    Foo(Foo const& other) { cout << "Foo copied" << endl; }
    ~Foo() { cout << "Foo destroyed" << endl; }
};

struct Bar {
    Bar() { cout << "Bar constructed" << endl; }
    Bar(Bar const& other) { cout << "Bar copied" << endl; }
    ~Bar() { cout << "Bar destroyed" << endl; }
};

void g(variant<reference_wrapper<const Foo>,reference_wrapper<const Bar>> foobar) {
    auto const* text = holds_alternative<reference_wrapper<const Foo>>(foobar) 
        ? "Foo" 
        : (holds_alternative<reference_wrapper<const Bar>>(foobar) 
            ? "Bar" 
            : "unknown");
    cout << "g(" << text << ")" << endl;
}


int main()
{
    Foo foo;
    Bar bar;
    g(foo);
    g(bar);
    return 0;
}

Output:

Foo constructed
Bar constructed
g(Foo)
g(Bar)
Bar destroyed
Foo destroyed
]]>
https://ikriv.com/blog/?feed=rss2&p=4882 0