How to properly compare performance of a prototype against a baseline Assume that we have a baseline software B and a new prototype P that I want to compare with B. Ideally, I want to show that P performs some orders of magnitude or X times faster than B (on average).

I have m queries/problems that I run on each software with a timeout T. I record the raw running times $b_1,\dots,b_m$ of B and $t_1,\dots,t_m$ of P.  It could be that for some (few) problems B is still faster than P, moreover it could be that there are very short times such as 0.01s or considerably longer ones, for instance, 3000s. Now my question is, what is a good measure to compare the performance of B and P quantitatively on average? 

A straightforward (but probably crude) measure could be just computing the average running times $b_a = \frac{1}{m}\sum_{i=1}^m b_i$ and $t_a = \frac{1}{m}\sum_{i=1}^m t_i$, and taking $\frac{b_a}{t_a}$.

A variation of this measure is taking the average of times when both systems didn't timeout and counting the number of timeouts, although not sure how to get just one measure from these four values. 

These two measures do not address one my concern related to the variance in the values of the times. For instance, for $m=2$, $b_1=2500$s, $t_1=8$s, $b_2=2000$s and $t_2=1000$s, the first measure is 4.4643. Does it mean that P performs on average 4 times faster? Would it be more reasonable to take the average of the normalised times $\frac{1}{m}\sum_{i=1}^m \frac{b_i}{t_i}$? In this case it would be equal 157.25 and, seems to me, would better reflect the performance gains. 

And again, a question is how to take timeouts into account properly.

I am sure that there should be standard approaches to comparing performance of two systems(for instance, databases), but I wasn't able to find anything quickly. I would also be grateful to see an explanation why one measure is better than the other, and what are the standard measures (at least on the scientific community).
The general answer is of course: "It depends on the problem and the final utilization of your software".

The first question you should answer is what makes a given version query time so variable ? Is it query dependent ? Does the software have some buffering between queries ? Maybe a ressource variable availability ?

Generally the performance of an algorithm is evaluated considering the worst query possible. Let's take an example, you need an algorithm to find where a function change of sign: 

You may loop on all points one by one or do a binary search. The former would sometimes performs faster if the searched point is one of the first. Nevertheless, in worst case it has to analyse all points whereas the latter finds the solution in logarithmic time.

Now if you have a timeout, the main metric you have is how many timeouts gets each solution. Maybe you even can identify what queries lead to timeout for each algorithm. In my opinion, there is no sense to compare average query time if some algorithm gets timeout more often.