[nylug-talk] x86-64 for 1GiB+ programs (especially in VMs) -- WAS: LOWMEM vs. HIGHMEM performance advantage?

[Eric Moore]

jh <jhlists at hirschman.net> writes:

> Eric Moore wrote:
>> jh <jhlists at hirschman.net> writes:
>>
>>>>>> b) some userland application stupidity (O(N^2) algorithm or somesuch)
>>>>> This is possible, but sadly, out of my hands.
>>>> do benchmarks on different dataset sizes and see if doubling the dataset
>>>> results in quadruple time to process?
>>> Hard to say. For example, one test set consists of 400k "units", and
>>> runs in 7 hours. Second test set consists of 400k units, and runs in
>>> about 8. Both use around 400ish megs of memory.
>>>
>>> Combining both test sets into an 800k unit test set gives us about a 22
>>> hour run time, using 900ish megs of memory.
>>>
>>> But... the application does shell out to do certain graphic-related
>>> operations. It is hard to say how much time is spent in the python app,
>>> and how much is spent in something it shells out to.
>>
>> Looks O(N^2) to me.  Try a 200k unit test set?  I'd guess 3-ish hours.
>>
>> something like: 0.1875 N^2 + 1.25 * N (N in 100k units)
>
> I'm sorry, not being much of a programmer - what does this mean?

Basically, that the program is doing something for every *pair* of
items in the data set, so that every time the data set doubles, the
run-time quadruples.

More realistically, most of the program does something for each item,
and part of the program does something for every pair, so it's not
quite an exact quadrupling when the data set doubles (since the part
that handles), so I took the 2 data points you gave me and worked out
an approximate equation to predict run times (assuming that overhead
is small, i.e. that a 10 "unit" test set runs in much less than an
hour).

Generally, if run time increases smoothly with increasing input sizes,
then you're looking at some kind of algorithmic complexity issue,
whereas if it jumps suddenly at some input size, you're looking at a
resource limit issue (crude ascii graph below).

               x                               x
                                         x
                                    x
            x

          x
         x                        x
       x                     x
    x                   x
x                   x

algorithmic         system limit
slowness            slowness

--
Eric