Right way to calculate performance about challenge_mail_filter

[feldgendler]

This would be the time per 200k messages, but I get your idea.

time_per_message = (t2 - t1) / 700000

[anthrax63]

@feldgendler And if my filter somehow works with xrlarge faster than large, i'll get the negative time %)

[feldgendler]

The time per message is not the best possible measure, either, because the overhead does matter. A solution with very short per-message time but a huge overhead would not necessarily be the best overall. What is “best” depends on the typical workload sizes, which is why we decided on 100k.

As I wrote, we could pick some kind of weighted sum which would serve as a better measure of performance. But we decided to stick with 100k because it's not entirely invalid, and would be the closest to what was originally announced.

[AgentRX]

Я за телефоном, поэтому буду по русски:-)

Смысл в том, что эти величины нельзя складывать без приведения к одному порядку.
Иначе прикладные затраты будут оказывать большое влияние на меньшие тайминги. Т.е. бОльшее время содержит в себе в 8 раз больше прикладных затрат, кроме затраты на обработку сообщения.

Т.е. правильная формула на 1 соообщение
time_per_message = (t1 + t2 / 8) / 200000

Но я не стал делать на 200к, т.к. это вносит ненужные округление и потерю точности. По этому для большей точности проще сравнивать без деления.

[anthrax63]

@feldgendler I do not fully understand. You choose do not measure performance for 800,000 messages, only 100,000?

[feldgendler]

Yes. We chose to stick with 100k messages, as was originally announced.

@AgentRX, I don't see why you chose this particular formula, t1 + t2/8. Let's assume the simplistic model that the time for n messages is C+k*n, where C is the constant overhead and k is time per message.

t1 = C + 100000*n
t2 = C + 800000*n
t1 + t2/8 = 1.125*C + 200000*n

Ranking by t1 relatively favors smaller overhead (1 microsecond per message is worth as much as 100 ms of overhead), ranking by t2 relatively favors shorter time per message (1 microsecond per message is worth as much as 800 ms of overhead). Your formula is somewhere in between (1 microsecond per message is worth as much as 178 ms of overhead). There are many ways to choose this ratio of relative importance of overhead and time-per-message, and t1 is as fair as anything else.

[AgentRX]

@feldgendler , I'll answer from home why I choose that formula in 2 hours. The mistake in your formula is the same C value for different amount of messages.

[AgentRX]

@feldgendler, so let me explain my formula.

I based on the next things:

1. The most users algorithms consists these parts:
   a. Preparing PDelay = Kprep

b. Preprocessing rules. PrepDelay = Rn * Ad * S(Rn)
c. Processing messages. ProcDelay = Mn * Kopt * S(Mn)
OR
b. Preprocessing messages. PrepDelay = Mn * Ad * S(Mn)
c. Processing rules. ProcDelay = Rn * Kopt * S(Rn)

where Mn - messages number, Rn - rules number,

Ad - algorithm delay
Kopt - is some optimization scalable constant which got because of preprocessing.
Kprep - some preparing delay.

So the next things are very important.
S(Mn) and S(Rn) - scalabilities for Rules and Messages

So, now we have formula for most algorithms:
SumDelay = Kprep + Rn * Ad * S(Rn)+ Mn * Kopt * S(Mn) (1a)
SumDelay = Kprep + Mn * Ad * S(Mn)+ Rn * Kopt * S(Rn) (1b)

If we speak about 100 rules and 100k/800k messages we can use simplier formulas:
SumDelay = Mn * Kopt * S(Mn) (2a)
SumDelay = Mn * Ad * S(Mn) (2b)

Now let's calculate t1 and t2 for 'a' case only (I think it's enougth):
t1 = 100 000 * Kopt * S1
t2 = 800 000 * Kopt * S2

The main your formula:
T = (t1 + t2) / 2 is wrong for scalability evaluation because you try to add different orders:
T = 50 000 * Kopt * S1 + 400 000 * Kopt * S2 = 50 000 * Kopt * (S1 + 8 * S2) (as you can see S2 is take effect 8 times more).

For example if we want to evaluate S2 and S1 values we should use:
Scal = S2 / S1 = t2 / (8 * t1) (smaller is better)

If we want to determine time speed we should use:
Tdet = (8 * t1 + t2) / 800 000 = Kopt * (S1 + S2) (smaller is better)

And finally we could use main formula for rating:
Rank = RankTime + RankScal (smaller is better)
where RankTime and RankScal is rate position by Scal and Tdet (from 1 to Num of participants)

[AgentRX]

@feldgendler , UPDATE. You can use this formulas to avoid collisions:
RankTime = RankTimeUser / RankTimeMin
RankScal = RankScalUser / RankScalMin

Rank = RankTime * RankScal (smaller is better)

PS. But if you have already chosen to stick with only 100k messages it's not actual now

[feldgendler]

Where did the constant part go in (2a) and (2b)?

[AgentRX]

@feldgendler , we can ignore them due to huge messages count. So these constants:
C1 = Kprep + Rn * Ad * S(Rn)
AND
C2 = Kprep + Rn * Kopt * S(Rn)

don't take essential value to the result because of:

1. 3 orders (10^3) different between Rn and Mn
2. 5 orders (10^5) different between Kprep and Mn

[feldgendler]

Where does this data come from, that they are negligible? Can you show your calculated values for a few submissions?

[AgentRX]

@feldgendler, because Kprep / Ad / Kopt variables are for one-few actions only.
If we have these formulas:
y1 = Tact * N + Tact * M + Tact
y2 = Tact * N2 + Tact * M + Tact

Tact - time for one logical action (process rule/message and so on),
N, N2 - messages number
M - rules number

and want for example to sum them:
y1 + y2 = Tact * N + Tact * M + Tact + Tact * N2 + Tact * M + Tact =
= 2 * Tact * ( M + 1) + Tact * N * (1 + N2/N)

In our case we'll get:
y1 + y2 = 2 * Tact * (100 + 1) + Tact * 100 000 * (1 + 8) =
= 202 * Tact + 900 000 * Tact

If we want to determine time for 1 rule we get:
Tone = (y1 + y2) / (N + N2) = (202 * Tact + 900 000 * Tact) / 900 000 =
= Tact + 202 * Tact / 900 000 = ~Tact

So next is small table for few participants:

Participant	Large	XLarge	Scal	Tdet (for 800k)	(t1 + t2) / 2	Rtime	Rscal	Rt+Rs
Roman Pletnev	187	2125	1,42	3621	1156	1	1,775	2,775
Evgeny Zeyler	219	1886	1,07	3638	1052,5	1,005	1,3375	2,3425
Yuri Kilochek	281	1802	0,80	4050	1041,5	1,118	1	2,118
Andrew Kashta	272	2453	1,13	4629	1362,5	1,278	1,4125	2,6905

As you can se my method has different result with yours but my method use scalable rating.

[feldgendler]

First, why do your formulas for y1 and y2 contain the same factors (Tact) for different things?

It should be:

  y1 = time_per_message*N + time_per_rule*M + startup_time
  y2 = time_per_message*N2 + time_per_rule*M + startup_time

Second, because we're not varying the number of rules, let's consider the terms containing M constant, so we'll include time_per_rule*M + startup_time into “C”. This produces the formulas I've shown previously:

  y1 = C + time_per_message*N
  y2 = C + time_per_message*N2

…and my reasoning stands valid.

[AgentRX]

@feldgendler, yes your formulas are right.

My main idea was to use both scalable and time criteria. I didn't want to rufute your formulas with constants:)

[feldgendler]

In real life, both C and time_per_message matter, and good engineering usually makes one or another trade-off between the two. As I have shown above, your proposal would shift thte balance of how much we relatively care about C and time_per_message, but any particular point of balance is a choice that is as good as any other.

[AgentRX]

@feldgendler , btw where is scalability factor in your formulas?

If use your formulas we'll get:
y1 = C + time_per_message * 1
y2 = C + time_per_message * 1000

Let's calculate scalability:
S = y2/(y1 * 1000) = (C + time_per_message * 1000)/(1000 * (C + time_per_message)) =
= (C + C * 1000 - C * 1000 + time_per_message * 1000) / (1000 * (C + time_per_message)) =>
S = 1 - 0,999 * C / (C + time_per_message)

If C > 0 and time_per_message > 0 than
that means that S is ALWAYS less than 1. But in real life scalability not linear and S could be more than 1.

Unfortinately it means formulas your suggested are wrong.

[feldgendler]

Please answer one question: in your model, is y linear in N? In other words, is y(N) a linear function (assuming M fixed)?

[AgentRX]

@feldgendler Of course not. If they were linear I wouldn't calculate Scal = S2 / S1

[feldgendler]

So your S() is some sort of nonlinear function? What do you think its graph looks like?

[AgentRX]

@feldgendler it's strange question. I'm not sure you understood S() meaning because S graph depends on filter.

If you want you can create more data sets and test filters on them.
Then calculate S1, S2...SN and draw it's graph.