1 The Name
CRTP(Curiously Recurring Template Pattern) is a C++ idiom in which a class X derives from a class template instantiation using X itself as template argument.
CRTP is used for static polymorphism, to avoid virtual functions, and give the compiler a chance to do the best optimization. Call of virtual function doesn't cost much, esp. with correctly predicted branch. but virtual function stop the inline optimization, and cost very much for floating point numeric algorithms.
CRTP is used for equipping object with interfaces based on a very smaller set of interfaces.
2 streambuf Example
std::streambuf
is a suitable example. Most of the public/protected functions is implemented based on virtual functions overflow
, underflow
, uflow
. Functions like xsgetn
and xsputn
with default implementation, based on overflow
, underflow
, uflow
. The pointer gptr
, pptr
are null if it's not modified by the derived object. Every time in the loop, xsgetn
/ xsputn
check the pointer range. If it's not empty(the pointer range modified by the derived object), memcpy
can be used for performance. If it's empty(or all exhausted), uflow
/ overflow
is called.
In some instances(char oriented),
gptr
and pptr
are always null, we can override the implementation without the check. And in some instances, the whole buffer is contiguous, then overflow
/ uflow
always return eof
. We can override the virtual functions with these conditions. But not the non-virtual one.
CRTP is suit to solve these two problems, without dynamic cost.
template <class Derived, class Char, class Traits> struct streambuf_base { // .... Derived & get_derived() { return *this; } const Derived & get_derived() const { return *this; } int_type snextc() { int_type r = traits_type::eof(); if (get_derived().sbumpc() != traits_type::eof()) r = get_derived().sgetc(); return r; } // .... };
The default
snextc
implementation uses sbumpc
and sgetc
, with get_dervied
prefix, the functions are resolved from derived to template base. Only if the derived doesn't override these functions, the template base's default are taken.
For example, stringbuf, alike to
std::stringbuf
, can implement snextc
, sbumpc
and sgetc
, just with one pointer comparation. All other default implementations will use this new-implemented version, thanks to get_derived
prefix.3 The Problem
The above is fine with just static polymorphism. The problems raise if we want the
streambuf_base
be compatible with std::streambuf
, to reuse all routines who only accepts std::streambuf
. So we must inherit from std::streambuf
.
We can't inherit from
std::streambuf
in derived
. If we do, any functions not re-implemented by derived will be ambiguous.
Inherit from
std::streambuf
in streambuf_base
is fine. But then the default implementations in streambuf_base
will override all in std::streambuf
. It's ok in these case, but not acceptable if we inherit from another base, which provides more resonable implementations than streambuf_base
.
So, what we want is an order of functions resolution. from derived to ancestor(std::streambuf in former case), and at last
streambuf_base
.4 The Solution
First, we must modify the
streambuf_base
to take another Ancestor
type parameters, and provides dummy
as default.
We can check whether
Ancestor
is dummy
in every streambuf_base
's function. If Ancestor
is not dummy
, we just call Ancestor
's version. Otherwise, the default implementation is taken.template <class Derived, class Char, class Traits, class Ancestor=dummy> struct streambuf_base : Ancestor { static const bool is_dummy = std::is_same<Ancestor, dummy>::value; typedef typename std::conditional< is_dummy, streambuf_base, Ancestor>::type ancestor_type; int_type snextc() { if (!is_dummy) return ancestor_type::snextc(); int_type r = traits_type::eof(); if (get_derived().sbumpc() != traits_type::eof()) r = get_derived().sgetc(); return r; } };
This introduces some other problems. If
Ancestor
is another one derived from streambuf_base
, the Ancestor::get_derived
is wrong. So if Ancestor::snextc
is taken, Ancestor::snextc
will call another sbumpc
and sgetc
, not the most-derived object's one.
One solution to this problem is using virtual functions. But make all functions be virutal is not a good solution.
Another solution is to redefine the
get_derived
. Add another MostDerived
paramter to streambuf_base
, and add most_derived_rebind
meta functor. For every Ancestor
, we check whether Ancestor::most_derived_rebind
exists. If it exists, streambuf_base
inherited from Ancestor::most_derived_rebind::template apply::type
instead of Ancestor
.template <class Derived, class Ancestor, bool=has_nested_type_most_derived_rebind<Ancestor>::value> struct streambuf_base_rebind_ancestor { typedef Base type; }; template <class Derived, class Base> struct streambuf_base_rebind_ancestor<Derived, Ancestor, true> { typedef typename Ancestor::most_derived_rebind::template apply<Derived>::type type; }; template <class Derived, class Char, class Traits, class Ancestor=dummy, class MostDerived=Derived> struct streambuf_base : streambuf_base_rebind_ancestor<MostDerived, Ancestor>::type { typedef typename streambuf_base_rebind_ancestor< MostDerived, Ancestor>::type _ancestor_type; typedef typename std::conditional< std::is_same<_ancestor_type, dummy>::value, streambuf_base, _ancestor_type>::type ancestor_type; MostDerived & get_derived() { return *this; } const MostDerived & get_derived() const { return *this; } struct most_derived_rebind { template <class T> struct apply { typedef streambuf_base<Derived, Char, Traits, Ancestor, T> type; }; }; };
5 The Result
With above
streambuf_base
, we can implements text format input/output routines in very higher performance, even faster than strtod
/ strtol
in experiments(locale is ignored).
The floating pointer converion is done by double-conversion, in shorted mode. For printf/scanf and stringstream, the precision is 20.
The random sequence for floating is generated by
random() / M_PI
and for long, just random()
.
For
fscanf
and fprintf
, the FILE*
is obtained by fmemopen
and open_memstream
.implements / type | long | float | double |
---|---|---|---|
streambuf_base | 45.13806234741213 | 87.06188110351565 | 193.94798608398446 |
strtox | 56.38690736389162 | 99.91599140930177 | 246.5969282989502 |
fscanf | 201.75892387390138 | 244.81490730285645 | 437.06397615051276 |
istringstream | 168.8839549407959 | 382.54306460571297 | 674.1460767364503 |
implements / type | long | float | double |
---|---|---|---|
streambuf_base | 109.96006123352053 | 221.0190715637207 | 285.9951219940186 |
snprintf | 290.8328487548828 | 1263.6021590270996 | 1915.7261646881104 |
fprintf | 279.30502569580074 | 1298.2731170043944 | 2073.194082229614 |
ostringstream | 122.75186352539063 | 1086.216874282837 | 1651.6398792114258 |
No comments:
Post a Comment