YetiSim Blog

A new class for memory management has been implemented for YetiSim, which is going to replace boost::shared_ptr.  This class has not yet been added to SVN.  I am migrating existing code to use the new MemoryManager singleton, and the design of the classes are being adjusted as I go along.  Rather than committing a broken YetiSim to trunk, or branching, I’ve decided to just do all the changes locally and introduce them all at once.

This represents a major change to YetiSim, since the class design is solidifying.  Real destructors are to be implemented, and new / delete calls are entirely confined to the MemoryManager class.  The library interface will consist entirely of references, while internal operations will use pointers or references.  The introduction of the MemoryManager has forced me to reconsider memory management for each class, and carefully document assumptions that have been made.  I read an analogy somewhere (maybe Meyers, maybe some docs, don’t remember) that dealing with memory is like dealing with toxic chemicals.  They are sometimes essential, however they must be treated with care.  I like this analogy, and I think about it a lot while I code.

Don’t get me wrong, boost::shared_ptr was very useful at the time, and perhaps my ignorance of Boost smart pointers is part of the reason I have migrated back to relatively simple references and pointers.  The use of smart pointers helped me create an initial version of YetiSim, and execute some simple simulations.  They were very useful for prototyping, and I feel that the overall quality of YetiSim has benefited from my experience with them.  But I also believe that they belong outside of the YetiSim library at a user level for now, and even then users must be careful of performance pitfalls.  The low overhead of boost::shared_ptr becomes astronomical in very large systems, with constant pointer operations.

I decided last night that I needed to implement a memory pool for YetiSim to boost efficiency. What I did not know, was that Threading Building Blocks already hid some of the details of pooling within the scalable_allocator. A response on the TBB forum indicated that the scalable_allocator was already capable of pooling, and that perhaps I did not need to implement my own classes for this purpose.

I already knew about the scalable_allocator, but there were some details that I did not know. First, that it implemented any form of pooling at all. You can learn more from this link. Another point that I did not know, was that it could be used as the allocator within an STL container. I knew that the cache_aligned_allocator could do this, but I was unaware that the scalable_allocator was also usable. This brings up a question: Does the cache_aligned_allocator pool memory in the same manner as the scalable_allocator? I would imagine it does, but I will have to investigate to find out.

This greatly simplifies the design of my MemoryManager class, in fact the first implementation of the class will merely wrap create and delete calls. At a later point, other magic may be done, however for now if the scalable_allocator works as promised, my memory management will be very simple. I still feel that it is good design to separate out memory management concerns, in case adjustments are required later.

As discussed in my previous blog, YetiSim’s memory management has formed a bottleneck.  I’m not entirely sure how to deal with this problem, so I’m considering abstracting the problem by creating a helper class called MemoryManager.  This would form  a common interface for memory management within YetiSim.  Hence future enhancements could be hidden behind a well defined interface.  Also, I think that issues of parallelism could be better handled in one place.

This would mean migrating from boost::shared_ptr to just regular old pointers.  This should be exception safe, because the MemoryManager is responsible for creating and deleting objects.  Hence, if an exception is thrown memory should not be lost because the MemoryManager class could be used to recover it, or to delete it if not required.  A memory pool could easily be implemented with the class, and the complexities of memory management could be entirely abstracted.

The MemoryManager would be implemented as a singleton class, just like the MasterScheduler.

Another possible advantage of abstracting memory management, is the migration of YetiSim to execution on clusters.  I’m not a cluster expert, however I know that managing memory that is spread across clusters would be different than managing the memory of a single computer.  One of the primary goals of YetiSim, is to be able to take a simulation from a single computer to execution on a large cluster.  This is a topic for another blog, but this longterm goal adds support to the argument for implementing a class to abstract the memory management.

I’m going to work on designing the memory management class tonight, and implement as much of it as possible.

Presently, YetiSim uses boost::shared_ptr for all pointer operations. Code execution profiling has revealed that incrementing and decrementing reference counts accounts for 50% of runtime. Smart pointers provide exception safety, and result in fairly safe code with minimal effort. Unfortunately the runtime cost has proven to be rather high. It could be argued that this is the cost of safety, however execution time is also highly important.

A few people have been surprised that the runtime cost of shared_ptr could be so high, and the reality is that YetiSim is a specialized application. Pointers are moved around within internal data structures frequently as simulation state changes, and this accounts for the high cost. The majority of the work performed by YetiSim, is done by moving pointers around. Each copy of a shared_ptr shares ownership of the pointed object, so that it does not disappear. The shared ownership is not strictly required in YetiSim, hence the high performance cost without advantage.

Strictly speaking, YetiSim would perform just fine without revising the design to reduce shared_ptr usage. Another hidden disadvantage of shared_ptrs may be how they affect parallelism. It may be that internally, shared_ptrs require the lock of a mutex for their use, otherwise the shared_ptr might be corrupted by threaded code. I’m not sure about the internals of the shared_ptr in threaded code, however this issue was hinted at on #boost. I feel that the potential performance gains achieved by redesigning classes which use shared_ptr justify the attention that such a redesign would require.

I would like to hide the use of real pointers within YetiSim, so that users do not see the added complexity. The use of pointers in C++ is not a super-advanced concept, but I want to provide a clean interface to users as much as possible. The target users of YetiSim will not be C++ gurus, they will be people who just need to write a simulation. Thus where possible, complexity has been shifted to YetiSim rather than to the library users.

Another bottleneck that has not yet shown itself, but surely is present, is the allocation of TaskContext objects used during parallel runs. The TaskContext structures are used by tbb::parallel_reduce for the join step, in which changes to the MasterScheduler are merged together. These structures have a clear() member function which resets them for later use, however presently they are deleted rather than reused. It would be better for TaskContext objects to be kept in a pool, so that objects could be allocated in larger chunks for use, and also reused rather than creating and deleting them.

It may also be prudent to build a pooling mechanism for the simulation entities themselves, if a large number of simulation entities were to be created and destroyed at runtime. This would require some interfaces to be implemented by the user directly, so this can wait for a while. It may be there are better ways to do this anyways. This is an issue that I will examine closer, but not for a little while.

VTune still does not work, but I’m working on that. In the mean time, Zach showed me how to use gprof. The results for a simulation run, of 100,000 clocks gave:
Each sample counts as 0.01 seconds.
% cumulative self self total
time seconds seconds calls s/call s/call name
14.99 17.35 17.35 137532699 0.00 0.00 boost::detail::atomic_exchange_and_add(int*, int)
12.22 31.49 14.15 114224959 0.00 0.00 boost::detail::atomic_increment(int*)
4.48 36.67 5.18 31662490 0.00 0.00 boost::detail::atomic_conditional_increment(int*)
4.06 41.37 4.70 std::bad_alloc::bad_alloc()
2.95 44.79 3.42 117077426 0.00 0.00 boost::detail::shared_count::~shared_count()
2.94 48.20 3.41 5342911 0.00 0.00 yeti::ThreadOfExecution::executeNodeLogic()
2.54 51.14 2.95 97465810 0.00 0.00 boost::detail::shared_count::shared_count(boost::detail::shared_count const&)
2.36 53.87 2.73 131417618 0.00 0.00 boost::detail::sp_counted_base::release()

The data is probably pretty messy to read, but the important finding is that the majority of execution time is spent on shared_ptr operations. This indicates that the internals of YetiSim have to be adjusted, so that as Zach suggests, we use const shared_ptr<T>& where possible.

I’ll be looking at the code in detail to determine how this problem can be addressed, and how performance can be improved. I suspect the solution will be to create containers which actually own the object, and use const references everywhere else. This solution would give the benefits of a shared_ptr, however it should help performance time.

YetiSim now has nightly builds available.  The latest code from trunk will always be available from http://www.yetisim.org/nightly/yetisim-nightly-build.tar.gz.  In addition, the source documentation at http://doxygen.yetisim.org will always reflect the documentation of the nightly build… that is until YetiSim has a stable release.

Some initial results are in, although there is still a lot more testing and tuning to do. This is the part of the project in which tools like Intel’s VTune are going to be critical in determining weak execution points of YetiSim. I’m using Gentoo, so VTune isn’t supported, but I’ll be installing the non-commercial version by following instructions I found here. I’ll have to install Ubuntu through VMWare, and follow the instructions from there… and hope for the best.

The simulation blogged about previously, with 100,000 clocks ticking for 60 seconds executed in31 seconds on my laptop with two processors. However with only one worker thread, the performance was 33 seconds. This implies that the parallelism didn’t buy us much, and that we need to improve how parallelism is performed. The same simulation executed for 8 minutes as implemented with SimPy. The performance advantage is largely due to the fact that YetiSim only passes smart pointers around, so operations are very cheap. The C++ compiler will play a role as well, and I intend to check YetiSim performance under the Intel C++ Compiler.

I believe that the bottle neck is in the scheduler… each simulation entity executes its state machine until a blocking event is encountered, in this case a wait for one second. The simulation clock is aligned along one second intervals, and this means that the worst case performance is hit every time. The simulation runs each ThreadOfExecution for a couple cycles, then stops because it’s blocked. The data structures then have to be merged back with the MasterScheduler copies, and this has a very high cost. Worse yet, this part of the simulation is executed serially. A parallel version of this operation would also improve performance. A response to a post on the Threading Building Blocks forums, suggested the growth of the vector requires memory movement. I’m going to try migrating to concurrent_vector to see what happens.

As a result of these experiments, I am going to factor out the scheduler algorithm from the design, and allow users to pop their own schedulers in or out at runtime. Basically, I’ve learned that one scheduler will not fit all simulations. I am going to include a library of schedulers that have been designed with certain characteristics, and simulation designers will be able to choose which one best increases their performance.

It might seem odd that it has taken about four months before YetiSim could execute a single simulation. Well, today is the day that things have changed. Today YetiSim executed a simulation of a wall clock, which counted up to one minute. That was nice, but I quickly throttled YetiSim to simulation 100,000 independent clocks to see the parallelism (it took 31 seconds to execute on my laptop). The workload split across two processors, and I can only presume that execution happened faster than without two processors. I will be doing some benchmarking of the scalability of YetiSim later tonight with a more sophisticated simulation, and comparing the times with a similar implementation in SimPy.  You can see below the state machine executed by YetiSim, note that it was also generated by YetiSim too!

Another blog will be coming soon with the changes that have been made to YetiSim, there have been a lot. However there is still a lot to do, for example right now I am installing the TBB scalable allocator to override new / delete. Next I will adjust all of the STL containers used in YetiSim to use the cache_aligned_allocator provided by TBB. I expect performance to increase slightly, because of better memory control.

I’ve also adjusted YetiSim to be capable of printing a full graphviz representation of a state machine… check out the state machine for the simulation I executed today. There is still a lot to do, the interfaces are not what they should be, things are still a bit more complicated than they should be. It will take time to make everything perfect, but for now YetiSim has executed its first ever simulation!

What makes an open source project successful? What can YetiSim learn from this? I’ve seen a lot of open source projects over the years, some rise up to great success and stay there. Some projects enjoy success for a while, then die off gradually as developers and users leave. Now that I have a blog, I decided to discuss what I think makes an open source project successful. I hope to learn from this in the construction of the open source community of YetiSim. I do not have much experience managing my own open source project yet, so I’m hoping to learn from others…. perhaps my lessons are too naive, but this is what I’ve learned regardless.

The Lessons:

1. Provide access to the source code, and have a source code management system like CVS or SVN.
2. Release early, release often.
3. Give the community of users and developers a voice.
4. Listen to your users, and pay attention to their needs. Be kind to them.
5. Provide good documentation for new developers, and encourage them.
6. A good community is a supportive one.
7. Try new paths, develop new methods. Push the envelope.

Lesson #1.

A critical component of open source software is naturally access to the source code. I have never seen an open source project that does not provide source code for download. However an equally critical component is a source code management system, like CVS or SVN. It is critical that members of the community are able to provide patches and bug fixes. I have worked on an open source project where the main developer would take snippets of code and ideas from the mailing lists, and incorporate them himself. This leads to burn out when so many people are there to help you. Also, with subversion it is simple for others to a generate a patch and submit to a mailing list. If I have to keep a tablet of paper beside me as I fix code, I will never have time to submit back my fixes. For this unnamed project I spent weeks modifying the sources for my employer, but the fixes were never shared because of the difficulty in getting the attention of the developer. The result was a stable system for us, with fixes to many problems others were experiencing on the mailing list. But they could never benefit from my hard work. Every time there was an upgrade in code from the project, I had to invest considerable time in re-applying my changes and testing. The moral of the story here, is to always have subversion access for others.  This way they can send patches to be reviewed and applied.

Lesson #2.

The catchy phrase release early, release often comes from Zach on #yetisim. It is imperative for an open source project to release something for the world to use as quickly as possible, and refine it with further development. This does not mean releasing buggy or incomplete software, this means releasing software that doesn’t have all the features everyone wants, but works pretty well. Open source software will not grow without a community, and a project will not gather a community without something for people to download and try. The released software does not have to be marked stable, which means the source is ready for prime time. The software should be ready for people to try and play with, but may have some rough edges. Projects which are hesitant to release something for people to try because the software is not yet perfect will not succeed (unless of course they are backed by corporations with deep pockets).  Also, it provides for a greater opportunity for the project to learn from mistakes early.

Lesson #3.

Give users and developers a voice. The users of a software package, and the developers of a package are equally important. A successful open source project will have methods of community communication, which might include mailing lists, bulletin boards, a wiki, or IRC. If users do not have a voice, developers cannot learn what is needed. Developers also cannot be sure they are developing something useful. Equally important is that developers are able to communicate. Projects often have separate areas for users and developers, and although this can lead to elitism, it is sensible. Developers need to concentrate on fixing issues, adding features, and learning new methods of solving problems. This can be difficult with the chatter that occurs on user forums, so it is sensible to separate to maintain concentration. A complete separation of concerns is a very bad idea, and indicates the potential doom of project. There must be a bridge between the users and developers. It does happen that a simple user question might indicate a massive design flaw, or indicate a new direction for the project.  There are usually people who decide to be the bridge themselves and participate actively in both development and user communications.

Lesson #4.

Listening to the users that you have given a voice might seem obvious, but it does happen that developers ignore their users. This can lead to elitism in the development team, and the result is a product that some people are not happy with. It is easy to say, “this is open source software, they get what they pay for.” Although I do not disagree with that statement, ignoring users can lead to users migrating to projects that satisfy their needs. This means doom for an open source project which relies upon a strong user community to succeed. There are times where users might be in error, or are suggesting something that is quite impossible with the given resources. It is okay to disregard the suggestions of a small percentage of users as being infeasible or specific to only their needs. But if a large percentage of the community wants a feature, it is time to learn what can be done to satisfy them. It is a bad idea to be stubborn about something for no reason, but quite alright to be realistic about the situation given current resources. Users are a very important aspect of a project. Most developers of a project start as users, and learn internals as they go. What I really mean, is that project developers should not ignore a feature request only because of their own objections and desire to ignore the users.  Users of software have to work with it, sometimes daily, and they often know best when it comes to features that will help them.

Lesson #5.

Provide good documentation and encouragement for new developers. Most open source projects are pretty good at this one. It is important that a project acquire as many developers as it can, and a good way to do this is to help interested developers learn as much as they can about your project. Naturally, good documentation facilitates people learning from the manuals directly. Without documentation potential developers have to post questions to mailing lists. This is not a bad thing, Google is fairly good at searching through mailing lists and becoming a sort of manual for a project. In fact most answers to questions I have about projects can be solved with a few careful Google searches. This highlights the rest of my lesson: provide encouragement to new users. This encouragement could be as simple as a thorough answer to the question posed, or words of encouragement to the user for their exploration of your project. Without thoughtful answers to questions posed on a mailing list, Google cannot help other users. It also creates an elitist group of those who are familiar with the code and those who are not. It is important to remember that tracing through the code of somebody else without documentation or help can be extremely hard. Most open source projects are good at this.

Lesson #6.

Build a supportive community by encouraging others and being helpful. This isn’t meant to be a mushy kind of statement, or to suggest that there will never be disagreements in projects. People are very important, and sometimes developers can forget that when they are under stress or are very busy. A supportive community will help attract users who are initially hesitant of trying something new. Look at the success of Ubuntu, which is extremely supportive of users. The support of other developers is important too. Finding a bug and fixing it, or trying a new design can be a very stressful experience. A good open source project is one that is appreciative of the help it receives. Some people, myself included, prefer open source development because others have the technical ability to praise your work. For me, recognition and appreciation is more important than salary.  Everyone likes a compliment or a recognition of their hard work, and it only takes a few minutes to give praise for hours of work.

Lesson #7.

Pushing the envelope is a very important aspect of open source projects. Part of what makes open source software so unique is the innovation that surrounds the projects. Anybody can download the source code, say to themselves “I don’t like this” and make radical changes that can then be tested and considered for inclusion in the main project. This type of exploration is very important, and leads to new methods and approaches. Some open source projects are open-ended, which means that they can continue to grow and adjust themselves. Other projects are simple implementations of specific things where stability is important, and the code won’t change much. The open-ended projects can explore new paths and try new things to enhance themselves. This keeps the development team interested, and the users anticipating new developments.

How YetiSim Learns From These Lessons

YetiSim is now about three months old. It has made an extraordinary amount of progress as a project in that time, although not really on a technical level. The source code of YetiSim has not changed much in the past two months, because the focus has been on the creation of a community. A wiki has been created to help potential developers and users learn about the project. This draws from the lesson of providing documentation. The source code for YetiSim is now available online for anonymous SVN checkout, and also for online browsing. This satisfies the requirement that others be able to see the source code to try it out, and to help with it. Today with the encouragement of Zach, the first snapshot of YetiSim was released, thus learning from the lesson that a project should release early. Users and developers do not have much of a voice in the project currently. I would like to setup a mailing list eventually, however this will not happen for a little while (I don’t even have email at yetisim.org yet). So YetiSim is a bit lacking in the voice regard right now.

Personally, as the main developer of YetiSim, some of these lessons are aimed at me. I have listened to Zach when he had suggestions for adjustments to the source code of YetiSim. His suggestions were acted on right away, the the code updated. I have been open to suggestions for the direction of my project, although I realize that this will get harder as the project becomes larger. I will make an effort to be supportive of users, and anyone who has questions about YetiSim. I do not have much time right now, but I certainly will make every effort possible to ensure that the project is making progress.  Of course, I will also ensure that the community surrounding YetiSim is a healthy one.

Today Zach Welch contributed a new build environment to YetiSim! He has become the first co-author of YetiSim. In fact, we met on #tbb a while ago, however I was not able to provide him with SVN access until the great server migration. The build environment has been holding YetiSim back, because I have not been able to commit my time to the internal YetiSim design. Rather, I have spent my time attempting to construct a sane build environment. With his contribution, I can move forward to constructing a test suite and proceed with development.

He also suggested that I do some code cleaning. YetiSim originally was coded in a hurry for submission to the TBB contest, and there are some messy details which required attention. In particular, I used the using directive in several header files. Another one of his suggestions was to pass a string into some class functions with const string& rather than just string.

I’m excited to have some help developing YetiSim, and someone to bounce some ideas off of. The next stage of development is the all important test framework. I’m not entirely sure how I am going to design the test suite for YetiSim, however that is a topic for a separate blog post. Oh, and on a side note come visit us at #yetisim on irc.freenode.net.