From mboxrd@z Thu Jan 1 00:00:00 1970 X-Spam-Checker-Version: SpamAssassin 3.4.4 (2020-01-24) on polar.synack.me X-Spam-Level: X-Spam-Status: No, score=-1.3 required=5.0 tests=BAYES_00,INVALID_MSGID autolearn=no autolearn_force=no version=3.4.4 X-Google-Language: ENGLISH,ASCII-7-bit X-Google-Thread: 109fba,baaf5f793d03d420 X-Google-Attributes: gid109fba,public X-Google-Thread: fc89c,97188312486d4578 X-Google-Attributes: gidfc89c,public X-Google-Thread: 1014db,6154de2e240de72a X-Google-Attributes: gid1014db,public X-Google-Thread: 103376,97188312486d4578 X-Google-Attributes: gid103376,public From: tim@franck.Princeton.EDU.composers (Tim Hollebeek) Subject: Re: Teaching sorts [was Re: What's the best language to start with?] Date: 1996/08/23 Message-ID: <4vjik9$eao@cnn.Princeton.EDU>#1/1 X-Deja-AN: 175927406 references: <01bb8f1b$ce59c820$32ee6fce@timhome2> <4vfk6b$i6h@krusty.irvine.com> <1996Aug22.165831.1@eisner> organization: Silicon Graphics, Inc. Mountain View, CA newsgroups: comp.lang.c,comp.lang.c++,comp.unix.programmer,comp.lang.ada Date: 1996-08-23T00:00:00+00:00 List-Id: In article <1996Aug22.165831.1@eisner>, kilgallen@eisner.decus.org writes: > In article , christian.bau@isltd.insignia.com (Christian Bau) writes: > > > Some time ago I did some experiments to find out how valuable benchmarks > > are. All I did was to program the standard method for multiplying two > > square matrices filled with double values. The number of assembly language > > instructions executed for matrices of size n x n was something like > > k1*n*n*n + k2*n*n + k3*n + k4, so you would expect that execution time is > > a monotonous function of n... > > > > On a real computer (PowerMac, no virtual memory, no background processes, > > nothing that would interfere with execution time), the _number of > > instructions per second_ did reproducably vary by a factor up to _seven_ > > when going from n to n+1 (for example, case n = 128 took seven times > > longer than cases n = 127 and n = 129). So for this computer, and this > > problem, an execution time of O (n**3) means "less than k*n**3, for some > > k>0, and for all n >= some n0", and nothing more This sort of behavior isn't that rare at all; I've seen it in quite a number of my benchmarks. An interesting one I found is that the time required to memcpy() 34 bytes is 5 times *less* than the time required to memcpy 30 bytes on my system. From a graph of time vs n, it appears that memcpy() switches algorithms at 32 bytes (I believe from a straightforward copy to something along the lines of Duff's device, since assymptotically it is very close to my routine using the latter method). --------------------------------------------------------------------------- Tim Hollebeek | Disclaimer :=> Everything above is a true statement, Electron Psychologist | for sufficiently false values of true. Princeton University | email: tim@wfn-shop.princeton.edu ----------------------| http://wfn-shop.princeton.edu/~tim (NEW! IMPROVED!)