{"id":1104,"date":"2015-05-18T23:20:43","date_gmt":"2015-05-19T06:20:43","guid":{"rendered":"http:\/\/www.elbeno.com\/blog\/?p=1104"},"modified":"2015-06-30T21:15:35","modified_gmt":"2015-07-01T04:15:35","slug":"the-lambda-trick","status":"publish","type":"post","link":"https:\/\/www.elbeno.com\/blog\/?p=1104","title":{"rendered":"“The Lambda Trick”"},"content":{"rendered":"

I just got back from C++Now<\/a>, an excellent conference where C++ template metaprogramming experts abound. A phrase I overheard often was “the lambda trick”. It’s a trick for speeding up compiles when templates get deep.<\/p>\n

Every C++ programmer knows that deep templates can slow down compilation. Most assume that this is because of excessive code generation (“code bloat”). But it turns out, I’m told, this isn’t actually the primary cause. As templates get deeper, type names get longer and longer, and it’s the compiler manipulating (hashing\/mangling) these internally that is a major cause of slow compilation.<\/p>\n

But when a compiler generates a closure type for a lambda, the name of that type doesn’t depend on its arguments. So it’s short, and it effectively truncates the long type name that was building up because of templates. Thus the lambda trick was born. In a post to the Boost developers’ mailing list<\/a> on June 6th 2014, Louis Dionne shared this technique that he’d discovered while programming the Hana library, a functional library implemented with heavy template metaprogramming.<\/p>\n

Let’s look at some code by way of explanation. The effect is most easily demonstrated with large tuples.<\/p>\n

\r\n#include \r\n#include \r\nusing namespace std;\r\n\r\nint main(void)\r\n{\r\n  auto len = tuple_size::value;\r\n  cout << len << endl;\r\n}\r\n<\/pre>\n
This is a very large tuple, resulting in a template type with a long name, and in fact I need to give GCC an argument to increase the template depth it can deal with. When I compile it (with GCC 4.9.2) this is the result:<\/p>\n
\r\n$ time g++ -std=c++1y -O2 -ftemplate-depth=2048 -c main.cpp -o tmp.o\r\n\r\nreal\t0m1.616s\r\nuser\t0m1.500s\r\nsys\t0m0.108s\r\n<\/pre>\n
1.6 seconds to compile that. And it produces the following assembly, optimized as you'd expect:<\/p>\n
\r\n0000000000000000 
:\r\n   0:\t48 83 ec 08          \tsub    $0x8,%rsp\r\n   4:\tbe 64 00 00 00       \tmov    $0x64,%esi\r\n   9:\tbf 00 00 00 00       \tmov    $0x0,%edi\r\n   e:\te8 00 00 00 00       \tcallq  13 ;\r\n   . . .\r\n<\/pre>\n
The constant 100 (0x64) is clearly visible there. And as expected, len<\/code> is a compile-time constant. I can use it in template expressions or as an array size, for instance.<\/p>\n
Now here is the same code with the \"lambda trick\" applied.<\/p>\n
\r\nint main(void)\r\n{\r\n  auto list = [] (auto... xs) {\r\n    return [=] (auto access) { return access(xs...); };\r\n  };\r\n\r\n  auto length = [] (auto xs) {\r\n    return xs([] (auto... z) { return sizeof...(z); });\r\n  };\r\n\r\n  auto len = length(list( 1,  2,  3,  4,  5,  6,  7,  8,  9, 10,\r\n                         11, 12, 13, 14, 15, 16, 17, 18, 19, 20,\r\n                         21, 22, 23, 24, 25, 26, 27, 28, 29, 30,\r\n                         31, 32, 33, 34, 35, 36, 37, 38, 39, 40,\r\n                         41, 42, 43, 44, 45, 46, 47, 48, 49, 50,\r\n                         51, 52, 53, 54, 55, 56, 57, 58, 59, 60,\r\n                         61, 62, 63, 64, 65, 66, 67, 68, 69, 70,\r\n                         71, 72, 73, 74, 75, 76, 77, 78, 79, 80,\r\n                         81, 82, 83, 84, 85, 86, 87, 88, 89, 90,\r\n                         91, 92, 93, 94, 95, 96, 97, 98, 99, 100));\r\n  cout << len << endl;\r\n}\r\n<\/pre>\n
The idea here is that list<\/code> is a lambda that hides the long template type. It's a generic lambda (C++14) and its closure object operator()<\/code> takes a variadic template argument. We can still pass in a function to work on the template - in this case length<\/code> - and once again, len<\/code> is known at compile time (tuple_size<\/code> has been replaced with sizeof...<\/code>). Compiling with -O2<\/code> gives identical code (although the lambda returned by list<\/code> looks like it captures, everything gets computed at compile time), but look at the time taken:<\/p>\n
\r\n$ time g++ -std=c++1y -g -O2 -c main.cpp -o tmp.o\r\n\r\nreal\t0m0.325s\r\nuser\t0m0.296s\r\nsys\t0m0.024s\r\n<\/pre>\n
It's 5x faster! The lambda hid the template, truncating the internal type name, so the compiler didn't have to deal with manipulating such long strings. That's \"the lambda trick\" in a nutshell.<\/p>\n","protected":false},"excerpt":{"rendered":"
I just got back from C++Now, an excellent conference where C++ template metaprogramming experts abound. A phrase I overheard often was “the lambda trick”. It’s a trick for speeding up compiles when templates get deep. Every C++ programmer knows that deep templates can slow down compilation. Most assume that this…<\/p>\n","protected":false},"author":2,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[22,8],"tags":[],"class_list":["post-1104","post","type-post","status-publish","format-standard","hentry","category-cpp","category-programming"],"_links":{"self":[{"href":"https:\/\/www.elbeno.com\/blog\/index.php?rest_route=\/wp\/v2\/posts\/1104","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.elbeno.com\/blog\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.elbeno.com\/blog\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.elbeno.com\/blog\/index.php?rest_route=\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"https:\/\/www.elbeno.com\/blog\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=1104"}],"version-history":[{"count":5,"href":"https:\/\/www.elbeno.com\/blog\/index.php?rest_route=\/wp\/v2\/posts\/1104\/revisions"}],"predecessor-version":[{"id":1109,"href":"https:\/\/www.elbeno.com\/blog\/index.php?rest_route=\/wp\/v2\/posts\/1104\/revisions\/1109"}],"wp:attachment":[{"href":"https:\/\/www.elbeno.com\/blog\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=1104"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.elbeno.com\/blog\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=1104"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.elbeno.com\/blog\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=1104"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}