In the interests of science, I wrote a small "file finder" using Boost.Filesystem and a comparable version using POSIX functions (e.g. stat, readdir, etc).

Wow, that's a fast test implementation!

Looking at the profiling output from the "finder-fs" program, it appears a bulk of the time is spent in fs::basic_path::operator/=() which may bear out Ion's fears.

Even if the string manipulation was not the most heavy part of the test, I would like to point out two ideas: -> Even if the filesystem is slower than returning a temporary object, that doesn't mean that you shouldn't optimize it. Your program is not alone in the computer, so when your program is waiting for I/O (surely via DMA) other processes are taking CPU, but when you create a lot of temporary strings you are stressing the memory allocator (so you can have more fragmentation in a long live program) and degrading overall system performance. Maybe your program is not much slower, but the CPU consumption is much higher. -> The good old C++ principle: "Pass heavy objects always by reference" is a very good advice to avoid performance problems. You can pass strings by value, but you never do that. But in my opinion this advice is also valid for the inverse sense: "Obtain heavy values always by reference". You never know how your code will be used, how many times your functions will be called. If you want your library to be useful even in situations that you don't predict, it's always helpful to use references. The difference is that passing parameters by reference does not change syntax whereas obtaining by values by reference is uglier. Caleb, I don't know if this is too much work but, can we know how many calls to "new" this application makes or even better, how many std::strings it constructs? Thanks and great job! Ion

Can you send the code of your "finder-fs" so that I can check it in visual 7.1 (non-reference counted implementation 16 small string optimization)? I suspect string/creation will be higher since you surely won't modify strings returned by path and reference counting will improve that. It's a shame I haven't got your 200 GB mp3 collection! Regards, Ion

Beman, is this on your radar screen at all? I last tried to ping you about it in March. To refresh, Boost.Filesystem seems to use the POSIX pathconf call excessively, which hurts performance when doing recursive operations like UNIX's find(1) command. On 3/7/06, Caleb Epstein <caleb.epstein@gmail.com> wrote:

On 3/6/06, Caleb Epstein <caleb.epstein@gmail.com> wrote:

...

On 3/4/06, Caleb Epstein <caleb.epstein@gmail.com > wrote:

...

On 3/4/06, Ion Gaztañaga <igaztanaga@gmail.com > wrote:

...

Now that filesystem is proposed for the standard I would like to ask boosters (and Beman, of course) if they find these performance concerns serious enough.

Perhaps if they were accompanied by some comparative performance benchmarks or profile analysis?

In the interests of science, I wrote a small "file finder" using Boost.Filesystem and a comparable version using POSIX functions ( e.g. stat, readdir, etc). The POSIX version runs MANY times faster than the Boost.Filesystem version (code attached). Note that the Boost version makes use of the "status" member of the directory iterator which is in CVS and is aimed at reducing the number of operating system calls that the library needs to make.

It seems that this profiling output might be slightly misleading. I don't think it is taking into account the time spent in system calls.

Using the Google CPU Profiler, I reran my tests on the Boost.Filesystemversion of the file finder and I find that the bulk of the runtime is spent not in string manipulation, but in calls to "statfs". It appears that this is coming from basic_directory_iterator::m_init, where it is calling pathconf:

#0 0x4020d9c0 in statfs () from /lib/tls/libc.so.6 #1 0x401dfb72 in pathconf () from /lib/tls/libc.so.6 #2 0x40022f89 in boost::filesystem::detail::dir_itr_first (handle=@0x8051184, buffer=@0x8051188, dir=@0xbfd8f79c, target=@0xbfd8f798) at libs/filesystem/src/operations.cpp:1178 #3 0x0804d231 in boost::filesystem::basic_directory_iterator<boost::filesystem::basic_path<std::string, boost::filesystem::path_traits> >::m_init ( this=0xbfd8f85c, dir_path=@0x80510d0) at operations.hpp:881 #4 0x0804d903 in basic_directory_iterator (this=0xbfd8f85c, dir_path=@0x80510d0) at operations.hpp:911 #5 0x0804ad72 in finder (root=@0xbfd8f57c, stats=@0xbfd8f8e0, recursive=true) at finder-fs.cpp:39 #6 0x0804b07d in main (argc=6, argv=0xbfd8f9b4) at finder-fs.cpp:90

This call accounts for 75% of the program's runtime according to Google's profiler (see attached PDF)

If I change the code in dir_itr_first to use the constant value NAME_MAX instead of retrieving this value via pathconf, the runtime for the Boost.Filesytem test and my "pure POSIX" version are nearly identical. Both run in about 0.8 seconds once the buffer cache has been seeded.

I understand why pathconf is being used for portability's sake, but it seems like its a real performance killer. Perhaps the NAME_MAX or MAXNAMLEN value could be used on platforms where it is defined?

-- Caleb Epstein caleb dot epstein at gmail dot com

-- Caleb Epstein caleb dot epstein at gmail dot com

"Chris Frey" <cdfrey@foursquare.net> wrote in message news:20060429021716.GA26100@foursquare.net...

On Thu, Apr 20, 2006 at 03:21:47PM -0400, Caleb Epstein wrote:

...

Beman, is this on your radar screen at all? I last tried to ping you about it in March.

To refresh, Boost.Filesystem seems to use the POSIX pathconf call excessively, which hurts performance when doing recursive operations like UNIX's find(1) command.

Performance has been a problem with Boost::Filesystem for at least a year. Back when I mentioned it, the "party line" :-) was that the API was top priority and performance would be something that could be looked at later.

With the standards committees looking at including Boost::Filesystem in TR2, I think performance is imporant enough to be looked at by now.

AFAIK, all performance issues have been resolved. The pathconf issues was only resolved recently, but the need for directory iteration to cache status was fixed quite a while ago, as were interface changes so that several status queries regarding the same file don't result in disk accesses unless so desired. So you may want to checkout the current CVS head to see if whatever performance problem you were seeing is still an issue. Part of the problem may be that the current Boost release process is so lengthy that changes made to CVS last Fall still haven't appeared in an official Boost release. I've got a proposal about ready to address that problem, and will post something in 10 days or so. --Beman

On 4/29/06, Beman Dawes <bdawes@acm.org> wrote:

"Chris Frey" <cdfrey@foursquare.net> wrote in message

...

With the standards committees looking at including Boost::Filesystem in TR2, I think performance is imporant enough to be looked at by now.

So you may want to checkout the current CVS head to see if whatever performance problem you were seeing is still an issue.

I have also found the current CVS code to be on par with my "100% pure POSIX" recursive file-finder. The run-times and of the two implementatoins are identical. In fact, I even found the Boost.Filesystem implementation to be more optimal in certain cases since it makes use of the dirent.d_type member to detect the is_directory-ness of an entry, where my naive POSIX code was always calling stat(2). This means fewer syscalls for the Boost version, which is a win. Thanks for the great library, Beman! -- Caleb Epstein caleb dot epstein at gmail dot com

Hi Beman,

As Caleb points out, it is premature optimizaton to talk about "hurting performance" in the absence of timings in realistic use scenarios.

That said, if you can come up with a realistic use case that really does show significant slow-down compared to some alternate interface, it would be worth talking about.

Ok. I see it like "premature pessimization", but you are right about a realistic use case. Scanning recursively a directory looking for files that have an extension (say for example, looking for mp3 files) is in my opinion a realistic use case. Obviously, looking for files will be slower than returning "path.leaf()" (although maybe the OS catches directory entries in memory) but apart from the speed, I think that the important point is the memory stress you force creating a temporary every time you want to obtain the name of the file. The filesystem operations are maybe slower but surely the OS is carefully avoiding heap fragmentation using internal pools, while the user is creating a lot of temporaries. I will try to implement this use case if you agree. The "path" class is also a class not related with disk operations (by the way, we can mount a filesystem in memory so operations can be fast, or it can represent a shared memory, following "Everything is a file" UNIX philosophy). Is it realistic to store a lot of path objects in a containers and request operations like leaf(), root(), etc...? I don't know. But I see the path class as a pseudo-container of strings representing a hierarchy. Path could represent a file or any other hierarchy in the operating system, because is quite generic.

...

Apart from this I see that path::iterator has a string member. dereference will return a reference to that member but an iterator is supposed to be a "lightweight" pointer-like abstraction, which is value-copied between functions. A string member, in my opinion, converts an iterator in a heavy class (that depends on the string length, but an small string optimization of 16 bytes is not going to help much).

That's an implementation detail. It isn't required by the spec, although that may be the most obvious way to implement the spec. An alternate implementation would be to keep a pool of directory entry objects and recycle them if performance was a concern. It would be great if Boost had a cache library to make such a strategy trivial to implement.

You are right. I need to concentrate on the interface. As a comment looking the code, since iterator returns a const string reference, you could also add a vector of strings to the path class, so that the iterator could be the const_iterator of the vector. You could avoid the string member and have trivial increment/copy operations. You are requesting more memory to the path class, though.

Thanks for the comments,

Thanks for your quick reply, Ion

...

That's an implementation detail. It isn't required by the spec, although that may be the most obvious way to implement the spec. An alternate implementation would be to keep a pool of directory entry objects and recycle them if performance was a concern. It would be great if Boost had a cache library to make such a strategy trivial to implement.

What kind of cache did you have in mind? Regex has an "Object Cache" (see boost/regex/pending/object_cache.hpp) that I always meant to submit for full Boost status but never got around to :-( It simply maps a "key" to an instance of an object constructed from the key: if the object already exists it returns it, otherwise it constructs a new one and caches it. Objects are returned as a shared_ptr<const Object> (the shared_ptr is needed for memory management, since neither the cache not the client have exclusive ownership on the object). Useage is simply: shared_ptr<const Object> obj = object_cache<Key, Object>::get( my_key, max_number_of_objects_to_cache); To be honest usefulness is pretty limited, and threading issues add a small performance hurdle, that means that "Objects" have to be fairly expensive to construct before it becomes useful. Still, there you go ;-) John.

...

Still, there you go ;-)

Rather than a cache that does A or a cache that does B, I'd rather see someone do a review of various cache features in the literature (or at least whatever Google can find), identify the most useful ones, and then design one or more classes (probably template based) that delivered that useful feature set.

For example, "Least Recently Used", "Least Frequently Used", and "Least Recently Added" are common replacement policies, but there are probably some others that are occasionally useful. I've used a scheme where entries are never flushed as long as there are any live references to them. Another way to approach a cache library design would be to collect a set of use cases, and then see what feature set would be needed to satisfy those use cases.

Caching is one of the fundamental ways to achieve improved performance. I'm a bit surprised it hasn't been more of a topic in Boost discussions, or in computer science in general.

That isn't a criticism of your object_cache; it is just that I think the topic deserves more than a single-solution approach.

Yep, I couldn't agree more: since I only needed one use case I only wrote one, and that's really why I haven't brought it forward for review. Or to put it another way I couldn't be bothered to go through all the possible caching policies ;-) John.

Nigel Stewart ha escrito:

...

...

Caching is one of the fundamental ways to achieve improved performance. I'm a bit surprised it hasn't been more of a topic in Boost discussions, or in computer science in general.

Here is an application for a C++ LRU datastructure in computer graphics: http://aim.adc.rmit.edu.au/phd/sgreuter/papers/graphite2003.pdf

In a nutshell, the datastructure is a fairly generic arrangement of std::list and std::map, but the replacement policy is fairly application-oriented.

Have you considered using Boost.MultiIndex as the core of your lru class? There's a MRU list class example in the same spirit at http://boost.org/libs/multi_index/doc/examples.html#example9 Joaquín M López Muñoz Telefónica, Investigación y Desarrollo

...

...

Caching is one of the fundamental ways to achieve improved performance. I'm a bit surprised it hasn't been more of a topic in Boost discussions, or in computer science in general.

Here is an application for a C++ LRU datastructure in computer graphics: http://aim.adc.rmit.edu.au/phd/sgreuter/papers/graphite2003.pdf

In a nutshell, the datastructure is a fairly generic arrangement of std::list and std::map, but the replacement policy is fairly application-oriented.

<Chuckles> That's exactly the same data structure I used to cache regex-traits classes and locales in boost/pending/object_cache.hpp. So it looks like at least two of us came up with the same idea... John.

Glad we didn't do anything too strange for our LRU cache!

Nope, actually I vaguely recall reading about something similar years ago when the STL was first released to the world, but no longer have the reference :-( John.

On Mon, 06 Mar 2006 11:25:49 -0600, Nigel Stewart wrote:

...

...

Caching is one of the fundamental ways to achieve improved performance. I'm a bit surprised it hasn't been more of a topic in Boost discussions, or in computer science in general.

Here is an application for a C++ LRU datastructure in computer graphics: http://aim.adc.rmit.edu.au/phd/sgreuter/papers/graphite2003.pdf

In a nutshell, the datastructure is a fairly generic arrangement of std::list and std::map, but the replacement policy is fairly application-oriented.

Related to this was some activity towards a boost circular buffer container... Which is something I intend to revisit, some shiny day...

Nigel

I developed a similar data structure for an LRU cache a while back. It is fairly basic - all you can do with it is check if a value exists, and add a value, but that was all that was required when I wrote it. The maximum size of the cache is determined at construction time. I did consider adding the ability to chain caches together, so you could have a small primary cache to test first, with a bigger secondary cache backing it up, but the amount of work involved compared to the prospective gain didn't seem worth it at the time. S> -- <<< Eagles may soar, but weasels don't get sucked into jet engines >>> 4:12pm up 82 days 23:54, 27 users, load average: 0.00, 0.00, 0.08 Registered Linux User #232457 | LFS ID 11703

Hi,

...

But when iterating through directories I find that that returning a temporary object that must allocate/copy/deallocate hurts my performance paranoia. Even with move semantics we have a an overhead:

On the other hand, I would guess that the actual OS and hard drive / network level operations take a lot more time than copying a few strings.

Yes. It's a wrong example, since a path has nothing to do with filesystem operations. A path (in the current implementation) is just a concatenation of strings representing a file or directory. Once path is formed there is no access to filesystem. For example, path.leaf() function is implemented as: return m_path.substr( leaf_pos( m_path, m_path.size() ) ); So path is a memory class. A "pseudo-container" of strings. Using path::iterator you can traverse those strings forming the path. Since you have to make conversions you can't return references like in normal containers in some cases, but returning values forces always a temporary string.

std::cout << it->root_name() << "append some data";

Who says you want to store the result? A temporary might be just fine.

But what if you want to store it?

...

Couldn't be better (although uglier) to take a reference to a string that will be filled?

void fill_root_name(string_type &root_name) const;

Really ugly! :-) It also assumes that the caller has somewhere to store the result. And the intention to keep it.

Couldn't we have both functions? Returning a copy forces always an extra allocation/deallocation and you can't avoid it. So maybe instead of replacing that function we can add a function saying we want to store that result in our string.

...

////////////////////////////////////////////////////////////////////

std::vector<std::path> paths; //fill with paths

std::path::string_type root_name;

root_name.reserve(PATH_LENGTH);

So now you are wasting space instead. :-)

...

This way we only allocate memory if we don't have enough place in our string. We can also reserve it beforehand to speed up code.

How do we know that speed is gained (and important), while space is cheaper?

Don't reserve anything, if you don't want to do it: std::path::string_type root_name; std::path::iterator beg = paths.begin(), end = paths.end(); for(; beg != end; ++it){ it->fill_root_name(root_name); } This will save (end-beg) string constructions and destructions. Is this a speed improvement. Well, that depends on: -> what ++it does (current boost path::iterator increment is expensive, but it does not need to, this is implementation detail) -> what it->does (currently returns the address of the internal string) -> the depth of the path But I think that filling a string instead of returning a temporary one is always faster. And there is another reason for avoiding allocation apart from speed: memory fragmentation. But as Beman has pointed out, I should not worry on implementation details, but on the interface. And the interface is forcing me to have temporaries in my code (for example like stringstream.str() function). How ofter will I call "root_name()", "leaf()" and others in my code? That will depend on the application type. My application maybe uses them once, but an antivirus scanning or a music jukebox constructing a song database will surely use them a lot. Regards, Ion

On 3/6/06, Nigel Stewart <ns@fluent.com> wrote:

...

But I think that filling a string instead of returning a temporary one is always faster. And there is another reason for avoiding allocation apart from speed: memory fragmentation.

Something not yet mentioned in this thread - the Qt QString provides a reference-counted "shallow-copy", (deep-copy on modification) mechanism that makes QString a lot more efficient than std::string in this kind of situation. Copying a QString is cheap, and sizeof(QString)==sizeof(int).

GNU's libstdc++'s std::string is reference counted as well. Has there been any boost proposal for alternative strings

to std::string?

There was a fixed_string library that was reviewed recently, but it was rejected. -- Caleb Epstein caleb dot epstein at gmail dot com