What is a secret of mpl::set?
I have implemented typeof+mpl::set based "unique" algorithm for overloads library. MPL associative containers are impressive, I must say. On an overload set containing 200 functions with unique signatures at positions 1, 2, 10, 39 and 200 new version compiles in 12 seconds on my notebook while for old version it's 47 seconds. What is a secret of mpl::set? I expected it's typeof-based like "at" for vectors, but it seems it's not. If it doesn't use typeof, may be I could try to put mpl::set idea into my algorithm? -- Alexander Nasonov
Alexander Nasonov wrote:
I have implemented typeof+mpl::set based "unique" algorithm for overloads library. MPL associative containers are impressive, I must say. On an overload set containing 200 functions with unique signatures at positions 1, 2, 10, 39 and 200 new version compiles in 12 seconds on my notebook while for old version it's 47 seconds. What is a secret of mpl::set? I expected it's typeof-based like "at" for vectors, but it seems it's not. If it doesn't use typeof, may be I could try to put mpl::set idea into my algorithm?
The tiny prototype that started all this is at: http://lists.boost.org/MailArchives/boost/msg53032.php In short, you don't need typeof for set. You can just use overloading to find out if the element is in there. For map, if you don't have typeof, you map each key type into a unique integer constant, and use that to do constant-time lookup via specialization, just like an mpl::vector would. Yeah, that part's pretty clever if I do say so myself. ;-) HTH, -- Dave Abrahams Boost Consulting http://www.boost-consulting.com
David Abrahams wrote:
The tiny prototype that started all this is at: http://lists.boost.org/MailArchives/boost/msg53032.php
Thanks, Dave. This gives me an idea. -- Alexander Nasonov
Alexander Nasonov wrote:
David Abrahams wrote:
The tiny prototype that started all this is at: http://lists.boost.org/MailArchives/boost/msg53032.php
Thanks, Dave. This gives me an idea.
Now I don't think I found a good idea, forget it. But I've tried another idea: If all functions have same arity, signatures of several functions can be deduced in one call. This improves performance for huge function sets. In the end of my post you'll find numbers for algorithm "unique" based on typeof and mpl::set with and w/o this optimization. Unique signatures are at 1, 2, 10, 39 and 200. Here we go: # init 1 # swapoff -a # cpuspeedy max # cat /proc/meminfo MemTotal: 516012 kB MemFree: 496272 kB Buffers: 740 kB Cached: 6308 kB SwapCached: 0 kB Active: 5612 kB Inactive: 3240 kB HighTotal: 0 kB HighFree: 0 kB LowTotal: 516012 kB LowFree: 496272 kB SwapTotal: 0 kB SwapFree: 0 kB Dirty: 76 kB Writeback: 0 kB Mapped: 2752 kB Slab: 6480 kB Committed_AS: 5540 kB PageTables: 164 kB VmallocTotal: 516020 kB VmallocUsed: 35040 kB VmallocChunk: 480456 kB # cat /proc/cpuinfo processor : 0 vendor_id : GenuineIntel cpu family : 6 model : 9 model name : Intel(R) Pentium(R) M processor 1300MHz stepping : 5 cpu MHz : 1296.046 cache size : 1024 KB fdiv_bug : no hlt_bug : no f00f_bug : no coma_bug : no fpu : yes fpu_exception : yes cpuid level : 2 wp : yes flags : fpu vme de pse tsc msr mce cx8 apic mtrr pge mca cmov pat clflush dts acpi mmx fxsr sse sse2 tm pbe tm2 est bogomips : 2555.90 $ g++ -v Reading specs from /usr/lib/gcc-lib/i686-pc-linux-gnu/3.3.4/specs Configured with: /var/tmp/portage/gcc-3.3.4-r1/work/gcc-3.3.4/configure --prefix=/usr --bindir=/usr/i686-pc-linux-gnu/gcc-bin/3.3 --includedir=/usr/lib/gcc-lib/i686-pc-linux-gnu/3.3.4/include --datadir=/usr/share/gcc-data/i686-pc-linux-gnu/3.3 --mandir=/usr/share/gcc-data/i686-pc-linux-gnu/3.3/man --infodir=/usr/share/gcc-data/i686-pc-linux-gnu/3.3/info --enable-shared --host=i686-pc-linux-gnu --target=i686-pc-linux-gnu --with-system-zlib --enable-languages=c,c++,f77 --enable-threads=posix --enable-long-long --disable-checking --disable-libunwind-exceptions --enable-cstdio=stdio --enable-version-specific-runtime-libs --with-gxx-include-dir=/usr/lib/gcc-lib/i686-pc-linux-gnu/3.3.4/include/g++-v3 --with-local-prefix=/usr/local --enable-shared --enable-nls --without-included-gettext --disable-multilib --enable-__cxa_atexit --enable-clocale=generic Thread model: posix gcc version 3.3.4 20040623 (Gentoo Hardened Linux 3.3.4-r1, ssp-3.3.2-2, pie-8.7.6) $ time g++ -I../../.. stress_unique.cpp Number of overloads uniform_row_earch universal_search passed to algorithm/total seconds seconds ------------------------- ----------------- ---------------- 200/200 8 13 300/300 15 26 400/400 24 43 500/500 35 65 600/600 49 94 700/700 66 128 200/500 15 27 300/500 21 39 400/500 28 52 Metaprogramming can process huge volume of data! -- Alexander Nasonov
Alexander Nasonov wrote:
Alexander Nasonov wrote:
David Abrahams wrote:
The tiny prototype that started all this is at: http://lists.boost.org/MailArchives/boost/msg53032.php
Thanks, Dave. This gives me an idea.
Now I don't think I found a good idea, forget it. But I've tried another idea: If all functions have same arity, signatures of several functions can be deduced in one call. This improves performance for huge function sets.
Great! :) But I don't really understand what you're talking about. Too much missing detail :(
In the end of my post you'll find numbers for algorithm "unique" based on typeof and mpl::set with and w/o this optimization. Unique signatures are at 1, 2, 10, 39 and 200.
And of course I don't know what the numbers mean either. -- Dave Abrahams Boost Consulting http://www.boost-consulting.com
David Abrahams wrote:
But I don't really understand what you're talking about. Too much missing detail :(
You're right, of course. I was under impression yesterday and posted it without any explanation. The cleanest way to explain it is an analogy with mpl unique algorithm. Let say we have mpl::vector700 of free unary function signatures with only few of them being unique. The algorithm I've tested is similar to this: typedef mpl::vector700< /* 700 signatures of free unary functions */ > signatures; typedef mpl::unique<signatures, is_same<_1,_2> >::type unique_signatures; My algorithm takes positions as mpl::range_c<int,1,701> and a class with 700 call-operators. It returns a positions of unique signatures: struct X { void operator()(overloads::overload_id<1>, int) const {} void operator()(overloads::overload_id<2>, char) const {} // ... void operator()(overloads::overload_id<10>, int***) const {} // ... void operator()(overloads::overload_id<200>, int*) const {} // ... void operator()(overloads::overload_id<700>, int*) const {} }; int main() { typedef unique<X, mpl::range_c<int,1,701>, mpl::identity<_1>, uniform_row_search>::type result; BOOST_MPL_ASSERT(( mpl::equal<result, mpl::vector_c<int,1,2,10,39,200> > )); } -- Alexander Nasonov
participants (2)
-
Alexander Nasonov -
David Abrahams