RE: [boost] String thought

From: Matthew Hurd (matt_at_[hidden])
Date: 2003-11-07 16:16:49

> On Behalf Of Pavol Droba
Hi Pavol,

> Subject: Re: [boost] String thought
> 
> On Fri, Nov 07, 2003 at 02:03:15PM -0800, John Torjo wrote:
> >
> > Matthew Hurd wrote:
> >
> > >Any lib related to Boost that uses expression templates for string or
> > >buffer
> > >operations to minimize the temporary objects?  Only thinking of
> > >concatenation but I guess it might apply elsewhere.
> > >
> > >Might be a neat addition to the string algorithm library.
> >
> > I would think so ;)
> > However, I'm not sure how realistic this could be.
> > Just consider this:
> >
> > for ( int i = 0; i < 10000; ++i)
> >     s += "s";
> >
> > In cases like this, expression templates would be useless, IMO.
> >
> > Anyway, Pavol, any thoughts?
> >
> 
> Expression templates might be an interesting idea, but I don't think that
> it
> fits into the scope of the string_algo library.
> This is more related as an extension to std::string. string_algo library
> does not work with str::string only and it is oriented towards algorithms.
> 
> Besides that, it could be hard to estimate the benefits, that such a
> framework
> could bring.
> There isn't realy much to optimize except to removing temporary objects.
> Given that fact, that string expression are usualy not very complicated
> and
> usualy contains only a small number of operations, it is easy to rewrite
> such
> an expression to use in-place variants if an optimalization is required.
> 
> Anyway, if somebody could come with such a framework, I'll be interested
> to see it.
> 
> Regards,
> 
> Pavol

Hacked up some code to see if there was much of a performance benefit with a
naïve implementation.  No memcpy or incrementing iterators, just s[i] to the
string...

I just got the numbers for a proxy for an "a = b + c + b + c;".  It seems
twice as fast compared to the standard way in VC7.1.

Might be worth writing some real code, but I can't see how it is possible to
inject the operator+ so that it works for std::strings...  Might have to be
left to the STL lib writers.

Any way, results and code below (VC7.1, 2.8G uP).

Regards,

Matt Hurd.

Results
-------
result b_ + c_ + b_ + c_ = and is this it and it doesn't seem much at all
and is this it and it doesn't seem much at all
time taken = 0.984
result b + c + b + c = and is this it and it doesn't seem much at all and is
this it and it doesn't seem much at all
time taken = 2.531
Press any key to continue . . .

/********************************************************************
        created:	2003/11/07
        created:	7:11:2003   20:56
        filename: 	\string_thing\string_thing.cpp
        author:		Matt Hurd
        
        purpose:	A quick hack for string concatenation
*********************************************************************/

// Code derived from 

// Disambiguated Glommable Expression Templates Reintroduced
// Geoffrey Furnish
//
// Originally in May 2000 C++ Report
// May be found http://www.adtmag.com/joop/crarticle.asp?ID=627 
//
// Well, not really but I read it just before writing the code...

#include <string>
#include <iostream>
#include <boost/timer.hpp>

namespace finray {

template< class StringProxy >
class string_concept
{
        StringProxy s_;

public:

        string_concept(const StringProxy& s) : s_(s) {}
        typedef typename StringProxy::value_type value_type;
        size_t size() const { return s_.size() 	}
        value_type operator[] (size_t i) const {return s_[i]; }

};

template< class StringBase >
struct et_string
{
        et_string(StringBase& s) : s_(s) {}

        typedef typename StringBase::value_type value_type;

        template <class StringProxy>
        StringBase& operator=( const StringProxy& sp )
        {
                const size_t size = sp.size();
                s_.resize(size);
                for( size_t i = 0; i < size; ++i )
                {
                        s_[i] = sp[i];
                }

                return s_;
        }

        size_t size() const
        {
                return s_.size();
        }

        value_type operator[] (size_t i) const
        {
                return s_[i];
        }

private:
                StringBase& s_;
};

template< class HeadString, class TailString >
struct string_list
{
        string_list(const HeadString& head, const TailString& tail)
                : head_(head), tail_(tail), head_size_(head_.size()),
total_size_(head_.size() + tail_.size() )
        {
                //std::cout << "constructing...\n";
        }

        size_t size() const
        {
                return total_size_;
        }

        typedef typename HeadString::value_type value_type;

        value_type operator[] (size_t i) const
        {
                return i<head_size_? head_[i] : tail_[i-head_size_];
        }

        
private:
        const HeadString& head_;
        const TailString& tail_;
        size_t head_size_;
        size_t total_size_;
};

template< class HeadString, class TailString>
string_list<HeadString, TailString> operator+ (const HeadString& lhs, const
TailString& rhs)
{
        return string_list<HeadString, TailString>( lhs, rhs);
}

template< >
string_list<std::string, std::string> operator+ (const std::string& lhs,
const std::string& rhs)
{
        return string_list<std::string, std::string>( lhs, rhs);
}

} // namespace finray

int main()
{

        using std::string;
        using namespace finray;

        string a;
        string b = "and is this it ";
        string c = "and it doesn't seem much at all ";

        finray::et_string<string> a_(a);
        finray::et_string<string> b_(b);
        finray::et_string<string> c_(c);

        const size_t limit = 1000000;

        double t_et, t_norm;
        boost::timer t;
        t.restart();
        for (size_t i = 0; i<limit; ++i) {
                a_ = b_ + c_ + b_ + c_;
        }
        t_et = t.elapsed();

        std::cout << "result b_ + c_ + b_ + c_ = " << a << "\n";
        std::cout << "time taken = " << t_et << "\n";

        t.restart();
        for (size_t i = 0; i<limit; ++i) {
                a = b + c + b + c;
        }
        t_norm = t.elapsed();

        std::cout << "result b + c + b + c = " << a << "\n";
        std::cout << "time taken = " << t_norm << "\n";

        system("PAUSE");
        return 0;
}

---
Outgoing mail is certified Virus Free.
Checked by AVG anti-virus system (http://www.grisoft.com).
Version: 6.0.536 / Virus Database: 331 - Release Date: 3/11/2003