Ayende @ Rahien

Hi!
My name is Ayende Rahien
Founder of Hibernating Rhinos LTD and RavenDB.
You can reach me by phone or email:

ayende@ayende.com

@

Posts: 5,949 | Comments: 44,546

filter by tags archive

UberProf performance improvements, or: when O(N^3 + N) is not fast enough


While working on improving the performance of the profiler, I got really annoyed. The UI times for updating sessions with large amount of statements was simply unacceptable. We already virtualized the list UI, so it couldn’t be that. I started tracking it down, and it finally came down to the following piece of code:

protected override void Update(IEnumerable<IStatementSnapshot> snapshots)
{
    foreach (var statementSnapshot in snapshots)
    {
        var found = (from model in unfilteredStatements
                     where model.Id == statementSnapshot.StatementId
                     select model).FirstOrDefault();

        if (found == null)
        {
            unfilteredStatements.Add(
                new StatementModel(applicationModel, statementSnapshot) {CanJumpToSession = false});
        }
        else
        {
            found.UpdateWith(statementSnapshot);
        }
    }

    if (snapshots.Any())
    {
        hasPolledForStatements = true;
        StatementsChanged(this, 
            new StatementsChangedEventArgs {HasPolledForStatments = hasPolledForStatements});
    }
}

This looks pretty innocent, right? At a guess, what is the performance characteristics of this code?

It isn’t O(N), that is for sure, look at the linq query, it will perform a linear search in the unfilteredStatements, which is an O(N) operation. *

At first glance, it looks like O(N*N), right? Wrong!

unfilteredStatements is an ObservableCollection, and guess what is going on in the CollectionChanged event? A statistics function that does yet another O(N) operation for every single added statement.

Finally, we have the StatementsChanged handler, which will also perform an O(N) operation, but only once.

protected override void Update(IEnumerable<IStatementSnapshot> snapshots)
{
    var hasStatements = false;
    foreach (var statementSnapshot in snapshots)
    {
        IStatementModel found;
        statementsById.TryGetValue(statementSnapshot.StatementId, out found);
        hasStatements = true;

        if (found == null)
        {
            unfilteredStatements.Add(new StatementModel(applicationModel, statementSnapshot) {CanJumpToSession = false});
            statementsById.Add(statementSnapshot.StatementId, found);
        }
        else
        {
            found.UpdateWith(statementSnapshot);
        }
    }

    if (hasStatements == false) 
        return;
    HandleStatementsOrFiltersChanging(true);
}

The changes here are subtle, first, we killed off the O(N) linq query in favor of an O(1) lookup in a hashtable. Second, unfilteredStatements is now a simple List<T>, and HandleStatementsOrFilterChanging is the one responsible for notifications. Just these two changes were sufficent from the O(N^3+N) that we had before to a simple O(N+N) (because we still run some statistical stuff at the end) which collapses so a simple O(N).

Once that is done, showing sessions with 50,000 statements in them became instantaneous.

* Yes, it is supposed to be O(M) because the unfilteredStatements.Count is different than snapshots.Count, but I am simplifying here to make things easier.

UberProf performance improvements


I mentioned before that I run into some performance problems, I thought it would be interesting to see how I solved them.

The underlying theme was finding O(N) operations are eradicating them. In almost all the cases, the code is more complex, but significantly faster

Old code New code
public static class TimestampExtensions
{
    public static void AddInPlace<T>(this IList<T> self, T model)
        where T : IHaveTimestamp
    {
        int index = self.Count;
        for (var i = 0; i < self.Count; i++)
        {
            if (self[i].Timestamp > model.Timestamp)
            {
                index = i;
                break;
            }
        }
        self.Insert(index, model);
    }    
}
public static class TimestampExtensions
{
    public static void AddInPlace(this IList<SqlStatement> self, SqlStatement model)
    {
        var timestamp = model.Timestamp;
        var index = self.Count;
        if (index > 0 && timestamp >= self[index - 1].Timestamp)
        {
            self.Add(model);
            return;
        }
        for (var i = 0; i < self.Count; i++)
        {
            if (self[i].Timestamp < timestamp) 
                continue;
            index = i;
            break;
        }
        self.Insert(index, model);
    }    
}

Here we optimize for the common case where we add the statement to the end of the list. We also changed from generic method with interface constraint to the actual type used. That allows the JIT to apply additional optimizations. That method alone was responsible for almost 10 minutes in my test runs.

Old code New code
var statement = session.Statements
    .Reverse()
    .Where(x => x.SessionId.Timestamp <= queryDuration.SessionId.Timestamp)
    .FirstOrDefault();
var statement = session.Statements.LastOrDefault();

session.Statements is already ordered by the statements timestamps. The code perform a slightly differently here, and it is less robust to async message streaming (when events that happened sequentially arrive in different order than they occured), but that is rare enough that I feel that the performance boost from this is acceptable.

Old code New code
public override void AfterAttachingToSession(
SessionInformation sessionInformation, SqlStatement statement) { var isSelectStatement = statement.IsSelectStatement; if (isSelectStatement == false) return; if (statement.RawSql == mySqlSelectLastIdentity) return; int countOfStatementsWithIdenticalSql = sessionInformation.Statements .Count(x => x.RawSql == statement.RawSql); if (countOfStatementsWithIdenticalSql <
configuration.MaxRepeatedStatementsForSelectNPlusOne) return; statement.AcceptAlert(AlertInformation.SelectNPlusOne()); }
public int GetCountOfStatementsByRawSql(string rawSql)
{
    int value;
    countsByRawSql.TryGetValue(rawSql, out value);
    return value;
}

public void AddStatement(SqlStatement statement)
{
    int count;
    if (countsByRawSql.TryGetValue(statement.RawSql, out count) == false)
        count = 0;
    countsByRawSql[statement.RawSql] = count + 1;
    
    statements.AddInPlace(statement);
    StatementsChanged();
}


public override void AfterAttachingToSession(
    SessionInformation sessionInformation, SqlStatement statement)
{
    var isSelectStatement = statement.IsSelectStatement;
    if (isSelectStatement == false)
        return;

    if (statement.RawSql == mySqlSelectLastIdentity)
        return;

    if (sessionInformation.GetCountOfStatementsByRawSql(statement.RawSql) < 
        configuration.MaxRepeatedStatementsForSelectNPlusOne)
        return;
    statement.AcceptAlert(AlertInformation.SelectNPlusOne());
}

On the left, we have the old code, that did the calculations manually. On the right, the two top methods will do the calculation up front, and then it is just a matter of reading it in the appropriate times.

Old code New code
protected void ClearStackTraceFromInfrastructureFrameworks(StackTraceInfo stackTrace)
{
    if (configuration.InfrastructureNamespaces == null)
        return;
    
    stackTrace.Frames =stackTrace.Frames.Where(
        frame =>
        {
            var isInfrastructureNamespace = 
                configuration.InfrastructureNamespaces.Any(
                ns => frame.Namespace != null && frame.Namespace.StartsWith(ns)
                );

            return isInfrastructureNamespace == false ||
                   configuration.NonInfrastructureNamespaces.Any(
                    ns => frame.Namespace != null && frame.Namespace.StartsWith(ns)
                    );
        }).ToArray();
}
public StackTraceProcessor(ProfilerConfiguration configuration)
{
    this.configuration = configuration;
    var sb = new StringBuilder();
    foreach (var infrastructureNamespace in 
        configuration.InfrastructureNamespaces ?? new List<string>())
    {
        sb.Append("(^")
            .Append(Regex.Escape(infrastructureNamespace))
            .Append(")|");
    }
    sb.Length = sb.Length - 1;
    namespacesToClear = new Regex(sb.ToString(),
        RegexOptions.Compiled | RegexOptions.IgnoreCase);
    sb.Length = 0;

    foreach (var infrastructureNamespace in 
        configuration.NonInfrastructureNamespaces ?? new List<string>())
    {
        sb.Append("(^")
            .Append(Regex.Escape(infrastructureNamespace))
            .Append(")|");
    }
    sb.Length = sb.Length - 1;
    namespacesToKeep = new Regex(sb.ToString(), 
        RegexOptions.Compiled | RegexOptions.IgnoreCase);
}

protected void ClearStackTraceFromInfrastructureFrameworks(StackTraceInfo stackTrace)
{
    if (configuration.InfrastructureNamespaces == null)
        return;

    stackTrace.Frames =
        stackTrace.Frames.Where(IsValidStackFrameMethod).ToArray();
}

private bool IsValidStackFrameMethod(StackTraceFrame frame)
{
    if (frame.Namespace == null)
        return true;
    if(namespacesToClear.IsMatch(frame.Namespace) == false)
        return true;
    return namespacesToKeep.IsMatch(frame.Namespace);
}

Interestingly enough, this code produced much better runtime performance, simply because, while it is more complex, the number of iterations that are happening are so much smaller.

Overall, the change result in order of magnitude or two difference for processing messages in the profiler pipeline.

EffectusIsolated features


Continuing in my exploration of the Effectus code base, which originated from my Building a Desktop To-Do Application with NHibernate article on MSDN Magazine, I wanted to talk today about separating features into individual pieces in the application.

Each feature in the Effectus application is built as an isolated unit, that has little to do with any other features. This is very clear when you look at how they are organized:

image 

Sidenote: In each feature, the component parts are named the same (Presenter, View, Model). This is intentional, since it make it that much harder to mix stuff from other features.

Every feature has a pretty rigid structure, defined by the application, and trying to reuse stuff between features is frowned upon and avoided, even if doing so can reduce duplication. As a good example, the Model for both CreateNew and Edit features are identical, but they are two different classes with no attempt to merge it up.

The reason for this is quite simple, treating each feature as an isolated unit bring us great benefits, we can have different developers working on different features without the chance of stepping on each other toes, it is very hard for one feature to break another, deploying new features is easier to handle, etc. Trying to apply DRY and consolidate common pieces of code would introduce dependencies between features, and that is a bad idea.

But what about communication between features? What about when one feature needs to call another?

As it turned out, it is quite easy to turn a lot of the inter feature communication into an indirect calls, using pub/sub. We gain the independence from dependencies using pub/sub, while maintaining the feel of a well integrated product for the user. For the rare cases of one feature calling another, I create a simple Call(“FeatureName”) mechanism (in the code, this is Presenters.Show(name) method) that all us to just explicitly invoke another feature, maybe with some initial arguments. A more complete implementation will handle even that using pub/sub, probably with an integrator class that would dispatch the appropriate event to start and invoke the feature(s) that want to handle it.

You can read more about the architecture principles behind this system in: Application structure: Concepts & Features

EffectusFatten your infrastructure


Continuing in my exploration of the Effectus code base, which originated from my Building a Desktop To-Do Application with NHibernate article on MSDN Magazine, I wanted to talk today about how to build an application infrastructure.

First, to be clear, I am not talking about infrastructure pieces such as caching, data access, etc. Those are generic concerns and you should be able to just get them from an off the shelve library. When I am talking about an application infrastructure, I am talking about the infrastructure code that you are going to need to write for a particular application. You are always going to have to do that, even if it is something as simple as just wiring the container together, or registering session handling, etc.

From my point of view, the point of the application infrastructure is to make writing the actual application features as simple as possible. Ideally, you want to make the infrastructure pieces handle everything that isn’t purely related to the feature you are implementing. The reason that an application infrastructure can do this while a generic infrastructure cannot is that an application infrastructure can make a lot of assumptions about the way the application is built.

Let us take the Main screen feature in Effectus, shall we, it will let us look at how this is implemented:

public Observable<int> CurrentPage { get; set; }


public
Fact CanMovePrev { get { return new Fact(CurrentPage, () => CurrentPage > 0); } } public Fact CanMoveNext { get { return new Fact(CurrentPage, () => CurrentPage + 1 < NumberOfPages); } } public void OnCreateNew() { Presenters.Show("CreateNew"); } public void OnActionsChoosen(ToDoAction action) { Presenters.Show("Edit", action.Id); } public void OnLoaded() { LoadPage(0); } public void OnMoveNext() { LoadPage(CurrentPage + 1); } public void OnMovePrev() { LoadPage(CurrentPage - 1); }

Looking the code, we can see that there are actually a lot of infrastructure playing a part here.

  • Automatic binding of On[Button Name]() methods to the button command.
    • Within this, enabling / disabling automatically using Can[Button Name] properties
  • Automatic binding of On[List name]Choosen(Item) to the selected item changed behavior on the list.
  • Automatic updates of property states using Fact.
  • Automatic updates of property values, using Observable.

There isn’t much to say about the automatic binding between UI actions and presenter methods, except that I think it is clear how this behavior reduce the level of infrastructure level code that you would have to write, test and maintain. But both Fact and Observable deserve a bit more explanation.

In the LoadPage() method, not shown here, we are updating the CurrentPage property, this will trigger invalidation of the all the facts bound to the value (CanMoveNext, CanMovePrev), which will force their re-evaluation. Since the infrastructure knows how to wire this up to the appropriate commands on the UI, this means that this will enable/disable the given controls automatically. What is more, look at the code. It is clear, concise and pretty easy to reason about and use.

I’ll leave the actual exploration of the implementation to you, it is fairly simple, but the idea is important. The Effectus application actually have more infrastructure code than it have code to implement its features. But that is a very small application. Just to give you an idea, the # of lines of code devoted to infrastructure in Effectus is about 600 LOC! In most applications, you probably wouldn’t even notice the amount of code that the infrastructure takes, but the effects are quite clear.

EffectusBuilding UI based on conventions


I waited for a while after my article was posted, to see if anyone caught on to some of the things that I did in the sample code that weren’t related to NHibernate usage. It seems that no one caught on to that, so I’ll try pointing them out explicitly.

The basic format of a feature in Effectus is this:

image

Each feature have a Presenter (business logic for the feature), a View Model, which is directly bound to the View and is the main way that Presenter has to communicate with the View. The main responsibility of the Model is to be bound to the UI, and allow the presenter to update it, but it is not quite enough.

The UI also need to raise events and handle user input. A common example is handling button clicks. You can’t really map them into Model behavior, at least not easily and in a way that make sense to the developers. Instead, I defined a set of conventions. As you can see in the picture, based on the name of the element, we match is with the appropriate execute method and the way to decide if the command can execute. Under the cover, we generate the appropriate ICommand instance, bound to the Presenter behavior.

image

If you look at the code, you can see that the conventions extend even to handling the selected item changed in a list box, including passing the newly selected instance back to the presenter. Those conventions are project specific, based on what the project need, and they result in a code base that is very easy to read and follow. Moreover, they result in a codebase that is relatively free from infrastructure concerns.

I am going to have a few more posts about Effectus, can you figure out what else I put in that code base?

How to write MEF in 2 hours or less


It took me a while to get around to this blog post, I promised Glenn that I would write it ages ago.

The title of this blog post, which is admittedly provocative, refer to a (I believe intentional) misinterpretation of a comment of mine in a MEF talk. It might also explain my general attitude about software in general.

MEF is a pretty big library, and it does a whole host of things. But when talking about it, there are specific features that keep getting mentioned over and over, probably because they are:

  • Really nice features.
  • Demo very well.

A good example of that is MEF ability to import new types on the fly. It is something really nice, but it isn’t something that is really impressive to me. Doing dynamic loading isn’t really hard. That has led me to make the comment that turned into the title of this post.

The actual comment I made was: “I can implement this feature (dynamic loading) in less than two hours.” The problem is that that was interpreted as saying that I can implement MEF itself in 2 hours (just to be clear, it isn’t possible). What is possible, however, is to implement interesting parts of MEF for a particular scenario in a short amount of time.

In fact, most of the time, I can implement the features that I find attractive in some software (not limited to MEF) faster than I can learn how to use that software in the first place. Granted, it may be a single purpose, only-works-under-the-following-set-of-assumptions implementation, but it will work, it will be faster out of the gate and it will limit the number of dependencies that I have to manage.

It is something that you have to consider, because sometimes you want to put those responsibilities at the hands of some other party because you don’t want to deal with that. Sometimes you explicitly want to do it yourself because giving up control on this thing (or adapting to the way some library does it) is not acceptable.

ÜberProf new feature: Fully keyboard enabled


For a long time, most of the work in the profiler (NH Prof, HProf, L2S Prof & EF Prof) could be done only with the use of the mouse. That annoyed a bunch of people, but it didn’t really bother me.  Rob fixed this recently, and I cannot believe what kind of a difference it makes.

Here are the shortcuts:

S Focus on Sessions tab header
T Focus on Statements tab header
D Focus on Details tab header
F Focus on Statistics tab header
Left / Right Move to the next / prev tab
Down / Up Move to next session / statement

Using those, you can use the common functionality of the profiler without touching the mouse.

Open Source Success Metrics


I got into a very interesting discussion with Rob Conery recently, talking about, among other things, the CodePlex Foundation. You can hear it TekPub’s Podcast #2, when it is out later this week. Tangential to our discussion, but very important, is how an Open Source project owner defines success for their project.

Usually, when people try to judge if an open source project is successful or not, they look at the number of users, and whatever the general response for the project is positive. But I am involved in a lot of open source projects, so you might say that I have an insider’s view on how the project owner view this.

Now, let us be clear, I am talking about OSS project that are being led by an individual or a group of individuals. There are different semantics for OSS projects that are being led by a company.

There are several reasons for individuals to be involved in OSS projects, those are usually:

  • Scratch an itch – I want to do something challenging/fun.
  • Need it for myself – This is something that the owner started because they needed it themselves and open sourced it for their own reasons.
  • Reputation building – Creating this project would give me some street cred.
  • I use it at work – Usually applicable for people joining an existing project, they use it at work and contribute stuff that they require.

We must also make a distinction between OSS adoption and OSS contribution. Typically, maybe a tenth of a percent of the adopters would also be contributors. Now, let us talk about the owner’s success metric again. Unless the owner started the project for getting reputation, the number of people adopting your project is pretty meaningless. I think that DHH , the creator of Ruby on Rails, did a great job describing the owner sentiment:

I'm not in this world to create Rails for you. I'm in this world to create Rails for me and if you happen to like that version of Rails that I'm creating for me, than you are going to have a great time.

Even if you are interested in OSS for reputation building, after a while, it stops being a factor. Either you got your reputation, or you never will. A good example of a project started to gain reputation is Rhino Mocks. And you know what, it worked. But I think that it is safe to say that I am no longer just that Rhino Mocks guy, so the same rules applies as for the other motivations.

So, what does it mean, from an owner perspective, when you ask if an OSS project is successful or not?  The answer is simple: it does what I need it to do.

I asked a popular OSS project owner the following question: What would your response be if I told you that I am taking a full page ad in the Times magazine proclaiming your stuff to be the best thing since sliced bread? You’ll get a million users out that that.

His response was: Bleh, no!

Tying it back to the discussion that I had with Rob, I feel that much of the confusion with regards to the CodePlex Foundation role is when you try to talk to projects led by individuals as if they were commercial enterprises. The goals are just completely different, and in many cases, adding more users for the project will actually be bad for the project, because it put a higher support cost for the project ream.

In the .NET ecosystem, most of the projects aren’t being led by a company. They are led by individuals. That is an important distinction, and understanding it would probably make it clear why the most common response for the CodePlex Foundation was: What is in it for me?

UberProf performance challenges


One of the things that the profiler is supposed to do is to handle large amount of data, so I was pretty bummed to hear that users are running into issues when they try to use the profiler in high load scenarios, such as load tests.

Luckily, one of the things that the profiler can do is output to a file, which let me simulate what is going on on the customer site very easily.

The first performance problem is that the profiler isn’t processing things fast enough:

image

The second is that there are some things that just totally breaks my expectations

image

There are solutions for those problems, and I guess that I know what I’ll be doing in the near future :-)

FUTURE POSTS

  1. The RavenDB Comic Strip: Part III – High availability & sleeping soundly - about one hour from now

There are posts all the way to May 28, 2015

RECENT SERIES

  1. The RavenDB Comic Strip (3):
    20 May 2015 - Part II – a team in trouble!
  2. Special Offer (2):
    27 May 2015 - 29% discount for all our products
  3. RavenDB Sharding (3):
    22 May 2015 - Adding a new shard to an existing cluster, splitting the shard
  4. Challenge (45):
    28 Apr 2015 - What is the meaning of this change?
  5. Interview question (2):
    30 Mar 2015 - fix the index
View all series

RECENT COMMENTS

Syndication

Main feed Feed Stats
Comments feed   Comments Feed Stats