[boost] Re: Re: Re: Any interest in a boost::glob() function?

From: Angus Leeming (angus.leeming_at_[hidden])
Date: 2004-10-05 03:18:18

Earlier, Gennadiy Rozental wrote:
AL>> No doubt there's lots of implementation details left, (like
AL>> using input_iterator_adaptor), but I think that this
AL>> using idea.
GR> You may use iterator_facade also. I just found that 
GR> implementing Input iterators using input_iterator_adaptor
GR> is easier. It's located in Boost.Test details derectory 
GR> along with some usage examples.
AL>> Am I on the right track?
GR> Definitely. Looking forward to see it implemented.

Later, Rob Stewart wrote:
AL>>>> It works, but is considerably slower than the function 
AL>>>> returning a list. No doubt profiling will help track 
AL>>>> down what I'm doing inefficiently.
RS>>> No doubt.
GR>> I do not see anything in iterator implementation that
GR>>  suggest inherent inefficiency.
RS> What he described sounded like he populated a container with the
RS> results and then iterated that.  Using the resulting iterator to
RS> populate another container would, thus, reduce efficiency.

Ahhhh. Now I understand you.

Actually, the glob_iterator I've implemented and have just posted 
here: 

http://www.devel.lyx.org/~leeming/glob.zip
(Docs can be viewed on line at:
http://www.devel.lyx.org/~leeming/libs/glob/doc/html/)

doesn't store anything but remains two to three times slower than the 
glob function that stores its results in a std::list.

$ cd libs/glob/example
$ time ./glob_function '*/*/*.hpp' '/home/angus/boost/cvs/' > /dev/null
count_operator 1997 count_regex_match 1997
real    0m0.095s
user    0m0.080s
sys     0m0.020s

$ time ./glob_iterator '*/*/*.hpp' '/home/angus/boost/cvs/' > /dev/null
count_operator 1997 count_regex_match 1997
real    0m0.241s
user    0m0.220s
sys     0m0.010s

I'm pretty sure I'm not doing anything daft. The 'count' data shows 
how many times I call the glob_predicate::operator() that decides 
whether a given file matches the globbing pattern. As you can see, 
this function is called the same number of times in each case. The 
algorithm to iterate over the files '*/*/*.hpp' is basically the same 
in the two cases, but the iterator version obviously has more 'if' 
statements in the inner loop. I guess that this is the killer and I 
don't think that there's anything we can do about it.

Soooooooooo... do we flag that one up as a valient effort and move on 
or can the iterator be as efficient as the function and I just 
haven't found the right algorithm?

Angu