robert zubek / blog

Viral Coefficient and Growth

The viral coefficient is a measure of how many new users are brought in by each existing user. It’s a quick and easy way to measure growth: if the coefficient is 1.0, the site grows linearly, and if it’s less than that, it will slow down. And if the coefficent is higher than 1.0, you have superlinear growth of a runaway hit.

In an invite-only situation (e.g. gmail closed beta), it’s easiest to calculate this directly, based on how many people are being invited by each new user, and how many of the invitees create new accounts themselves. The viral coefficient is simply:

v = new user invites accepted / new users
   = accepts_t / δp_t-1

where δp_t denote the number of new users who join in time slice t (ie, the increase in population between p_t-1 and p_t). 

But most sites have an open account creation policy. For those, we’ll have to estimate population acceleration from raw population deltas. Let’s assume that each accepted invite is quivalent to creating a new account at the next time slice. Then we can estimate virability as:

v ≈ δp_t / δp_t-1
   = (p_t - p_t-1) / (p_t-1 - p_t-2)

which is an acceleration metric, easy to compute from historical data. 
 

Population Forecasting 

Viral estimate calculated as momentary acceleration will fluctuate over time. But we can use it for some short term forecasting.

To calculate expected future population p_t some t steps in the future, given the viral coefficient and present population p₀, we first invert the above:

δp_t = v δp_t-1 = … = v^t δp₀

and plug this right back in:

p_t = δp_t + p_t-1
    = Σ_k≤t  δp_k + p₀
    = Σ_k≤t  v^k δp₀ + p₀

This describes a geometric series. When v ≠ 1, p_t  = δp₀ (1 - v^t+1) / (1 - v) + p₀ 

Here are the results of a little benchmark I ran a while back, trying to figure out how expensive are the different primitive operations in Flash 9 (ie. bytecode compiled ActionScript 3).

Quick note on methodology: I ran these primitive operations in a tight loop of a few million iterations, to get average runtime per iteration (subtracting out the runtime of an empty loop, of course), and then repeated this a handful of times. I’m reporting mean numbers below, and standard deviations only when they’re unusual.

The raw times aren’t very important (benchmarks were done on an old Athlon 2400+ that’s living out its retirement years under my kitchen table). But the proportional differences between them can be surprising - especially the order-of-magnitude ones.

Now, on to some delicious results!

Numbers

Some obligatory numeric operation benchmarks:

Signed integer addition: 6.3ns
Signed integer multiplication: 13.1ns
Signed integer division: 15.3ns

Unsigned integer addition: 9.6ns
Unsigned integer multiplication: 28.3ns
Unsigned integer division: 32.4ns

Double addition: 9.4ns
Double multiplication: 7.4ns
Double division: 7.1ns

There’s really no reason not to use doubles for virtually all math operations; they’re much cheaper (possibly because they don’t try to do any bounds checks).

The one exception would be array indexing, where one really wants to guarantee that the index is an integer. Fortunately, conversions are pretty inexpensive as well:

Integer -> Number conversion: 7.3ns
Number -> integer conversion: 5.0ns

Now for some math library operations:

Math.sqrt: 137.9ns
Math.sin: 183.3ns
Math.round: 197.9ns
Math.floor: 160.2ns

That’s pretty good, much faster than regular function calls (see below) - probably because these are native, instead of bottoming out in bytecode like everything else. Still, a square root is on the order of about 20 times more expensive than arithmetic operations.

Function Calls

Speaking of which, here are the regular function calls - just the call, with no body:

Function call (no arguments): 239.8ns
Function call (unary): 257.6ns
Function call (binary): 269.0ns

Pretty standard stuff, with cost increasing (linearly?) as a function of the number of arguments. It’s more expensive than calling native functions, but not significantly higher. Still, it does put an upper limit of about 4 million function calls a second, or 100,000 calls per frame, on my test machine.

By the way, this was completely unexpected:

Anonymous function declaration: 11368.8ns (s = 105.3)

Creating an instance of an anonymous function costs 11 microseconds? Ouch. I’m a big fan of treating everything as lists of data, and map-filtering them with ad-hoc anonymous functions. But now I have to be more careful.

Arrays

For array access, I’ve only checked access of a single array element, many times over. Some numbers:

Writing from variable to array: 69.0ns, s = 1.9
Reading from array to variable: 106.3ns, s = 105.5
Reading from object with integer keys: 72.0ns, s = 1.9
Reading from object with string keys: 242.8ns, s = 1.8

First, I thought it was interesting that an object with integer keys is just as fast as an array with integer keys, suggesting a shared underlying implementation. An object with string keys is slower, however.

Two, the array reading measurement is not only pretty high, it also has a very high standard deviation, as if the measurements included a few really expensive outliers. Am I running into intermittent delays when accessing array data; perhaps cache stalls?

Finally, some results trying to iterate over a large array:

Iteration over array using ‘for each’ special syntax: 8576.8ns, s = 2.4
Iteration over array using int: 20483.5ns, s = 4.6
Iteration over array using uint: 19665.3ns, s = 2.8
Iteration over array using forEach: 31416.8ns, s = 47.7

I’m not susprised that code inside a for loop is faster than code inside a function called via forEach. What I am surprised about, is that the “for each ( … )” special form is much faster than the standard “for ( ; ; )” iteration with array lookup. That’s not what you’d expect in a language like C; I’m curious what’s going on under the hood.