Message-ID: <4756DA3D.1060708@argo.co.il>
Date:	Wed, 05 Dec 2007 19:05:01 +0200
From:	Avi Kivity <avi@...o.co.il>
To:	Willy Tarreau <w@....eu>
CC:	Andi Kleen <andi@...stfloor.org>,
	Kyle Moffett <mrmacman_g4@....com>,
	Lennart Sorensen <lsorense@...lub.uwaterloo.ca>,
	Ben Crowhurst <Ben.Crowhurst@...llatravel.co.uk>,
	linux-kernel@...r.kernel.org
Subject: Micro vs macro optimizations (was: Re: Kernel Development & Objective-C)

Willy Tarreau wrote:
> Hi Avi,
>
> On Tue, Dec 04, 2007 at 11:07:05PM +0200, Avi Kivity wrote:
>   
>> Willy Tarreau wrote:
>>     
>>>>>>   
>>>>>>        
>>>>>>             
>>>>> With 10Gbit/s ethernet working you start to care about every cycle.
>>>>>
>>>>>      
>>>>>           
>>>> If you have 10M packets/sec no amount of cycle-saving will help you.  
>>>> You need high level optimizations like TSO.  I'm not saying we should 
>>>> sacrifice cycles like there's no tomorrow, but the big wins are elsewhere.
>>>>    
>>>>         
>>> Huh? At 4 GHz, you have 400 cycles to process each packet. If you need to
>>> route those packets, those cycles may just be what you need to lookup a
>>> forwarding table and perform a few MMIO on an accelerated chip which will
>>> take care of the transfer. But you need those cycles. If you start to waste
>>> them 30 by 30, the performance can drop by a critical factor.
>>>
>>>  
>>>       
>> I really doubt Linux spends 400 cycles routing a packet.  Look what an 
>> skbuff looks like.
>>     
>
> That's not what I wrote. I just wrote about doing forwarding table lookup
> and MMIO so that dedicated hardware NICs can process the recv/send to the
> correct ends. If you just need to scan a list of DMAed packets, look at
> their destination IP address, lookup that IP in a table to find the output
> NIC and destination MAC address, link them into an output list and waking
> the output NIC up, there's nothing which requires more than 400 cycles
> here. I never said that it was a requirement to pass through the existing
> network stack.
>   

If you're writing a single-purpose program then there is justification 
to micro-optimize it to the death.  Write it in VHDL, even.  But that 
description doesn't fit the kernel.

>   
>> A flood ping to localhost on a 2GHz system takes 8 microseconds, that's 
>> 16,000 cycles.  Sure it involves userspace, but you're about two orders 
>> of magnitude off.
>>     
>
> I don't see where you see a userspace (or I don't understand your test).
>   

ping -f -q localhost; the ping client is in userspace.

> On traffic generation I often do from user space, I can send 630 k raw
> ethernet packets per second from userspace on a 1.8 GHz opteron and PCI-e
> NICs. That's 2857 cycles per packet, including the (small amount of)
> userspace work. That's quite cheap.
>
>   

Yes, it is.

>> This happens very often in HPC, and when it does, it is often worthwhile 
>> to invest in manual optimizations or even assembly coding.  
>> Unfortunately it is very rare in the kernel (memcmp, raid xor, what 
>> else?).  Loops with high iteration counts are very rare, so any 
>> attention you give to the loop body is not amortized over a large number 
>> of executions.
>>     
>
> Well, in my example above, everythin in the path of the send() syscall down
> to the bare metal NIC is under high pressure in a fast loop. 30 cycles
> already represent 1% of the performance! In fact, to modulate speed, I
> use a busy loop with a volatile int and small values.
>
>   

Having an interface to send multiple packets in one syscall would cut 
way more than 30 cycles.

>>>>    
>>>>         
>>> You are forgetting something very important : once you start stacking
>>> functions to perform the dirty work for you, you end up with so much
>>> abstraction that even new stupid code cannot be written at all without
>>> relying on them, and it's where the problem takes its roots, because
>>> when you need to write a fast function and you notice that you cannot
>>> touch a variable without passing through a slow pinhole, your fast
>>> function will remain slow whatever you do, and the worst of all is that
>>> you will think that it is normally fast and that it cannot be written
>>> faster.
>>>
>>>  
>>>       
>> I don't understand.  Can you give an example?
>>     
>
> Yes, the most common examples found today involve applications reading
> data from databases. For instance, let's say that one function in your
> program must count the number of unique people with the name starting
> with an "A". It is very common to see "low-level" primitives to abstract
> the database for portability purposes. One of such primitives will
> generally be consist in retrieving a list of people with their names,
> age and sex in one well-formated 3-column array. Many lazy people will
> not see any problem in calling this one from the function described
> above. Basically, what they would do is :
>
>  count_people_with_name_starting_with_a()
>     -> array[name,age,sex] = get_list_of_people()
>          -> while read_one_people_entry() {
>                alloc(one_line_of_3_columns)
>                read then parse the 3 fields
>                format_them_appropriately
>             }
>     -> create a new array "name2" by duplicating the "name" column
>     -> name3 = sort_unique(name2)
>     -> name4 = name3.grep("^A")
>     -> return name4.count
>
> Don't laugh, I've recently read such a horrible thing. It was done
> that way just because it was easier. Without the abstraction layer,
> the coder would have been forced to access the base anyway and would
> have seen an added value into just counting from the inner while
> loop, saving lots of copies, greps, sort, etc... :
>
>  count_people_with_name_starting_with_a() {
>       count = 0;
>       while read_one_people_entry() {
>          read the 3 fields into a statically-allocated buffer
>          if (name[0] == 'A') count++;
>       }
>       return count;
>  }
>
> I'm not saying that the above was not possible, just that it's
> 1000% easier to do the former without even having to think that
> the final code uses such horrible things. 

Your optimized version is wrong.  It counts duplicated names, while you 
stated you needed unique names.  Otherwise the sort_unique step is 
completely redundant.

Databases are good examples of where the abstraction helps.  If you had 
hundreds of millions of records in your example, you'd connect to a 
database, present it with an ASCII string describing what you want, upon 
which it would parse it, compile it into an internal language against 
the schema, optimize that and then execute it.  Despite all that 
abstraction it would win against your example because it would implement 
the inner loop as

    open index (by name)
    seek to 'A'
        while (current starts with 'A')
                ++count (taking care of the uniqueness requirement if 
needed)
    close index

Thus it would never see people who's name begins with 'W'.  If the 
database had a materialized view feature, and this particular query was 
deemed important enough, it would optimize it to

    open materialized view
    read count
    close materialized view

The database does all this while allowing concurrent reads and writes 
and keeping your data in case someone trips on the power cord.  You 
can't do that without a zillion layers of abstraction.


>> There are two cases where abstraction hurts performance: the first is 
>> where the mechanisms used to achieve the abstraction (functions instead 
>> of direct access to variables, function pointers instead of duplicating 
>> the caller) introduce performance overhead.  I don't think C has any 
>> advantage here -- actually a disadvantage as it lacks templates and is 
>> forced to use function pointers for nontrivial cases.  Usually the 
>> abstraction penalty is nil with modern compilers.
>>
>> The second case is where too much abstraction clouds the programmer's 
>> mind.  But this is independent of the programming language.
>>     
>
> Agreed. But most often, the abstraction prevents the user from accessing
> some information directly and that becomes nasty. I remember when I was
> a teen, I wrote a program designed to inventory what you had in your PC,
> and run a few performance tests. It ran in those semi-graphical DOS mode
> where you use graphics characters to draw boxes. I initially wrote all
> the windowing code myself and it ran perfectly. I once decided to rewrite
> it using TurboVision, the windowing framework from Borland (it was written
> in TurboPascal). I made intensive use of the equivalent of a putchar()
> function to write text in a window. You cannot imagine my pain when I
> ran it on my old 8088, it wrote at the speed of a 1200 bps terminal. I
> then tried to find how to write faster, even by accessing the window
> buffer directly. I couldn't. I had to reverse-engineer the internal
> structures by debugging memory contents in order to find the pointers
> to the window buffer to write to them directly. After this disastrous
> experience with abstraction, I thought "never that crap again".
>
>   

If the abstraction if badly written, and further you cannot change it, 
then of course it hurts.  But if the abstraction is well written, or if 
it can be fixed, then all is well.  The problem here is not that 
abstractions exist, but that you persist in using a broken API instead 
of fixing it.


>>> Every cycle burned is definitely lost. The time cannot go backwards. So
>>> for each cycle that you lose to laziness, you have to become more and more
>>> clever to find out how to write an alternative. Lazy people simply put
>>> caches everywhere and after that they find normal that "hello world" 
>>> requires
>>> 2 Gigs of RAM to be displayed. 
>>>       
>> A 100 byte program will print "hello world" on a UART and stop.  A 
>> modern program will load a vector description of a font, scale it to the 
>> desired size, render it using anti aliasing and sub-pixel positioning, 
>> lay it out according to the language rules of whereever you live, and 
>> place it on a multi-megabyte frame buffer.  Yes it needs hundreds of 
>> megabytes and lots of nasty algorithms to do that.
>>     
>
> What I'm complaining about is that when you don't want those fancy things,
> you still have them to justify the hundreds of megs. And even if you manage
> to print to stdout, you still have a huge runtime just in case you'd like
> to use the fancy features.
>
>   

That's life.  The fact is that users demand features, and programmers 
cater to them.  If you can find a way to provide all those features 
without the bloat, more power to you.  The abstractions here are not the 
cause of the bloat, they are the tool used to provide the features while 
keeping a reasonable level of maintainability and reliability.


>>> The only true solution is to create better
>>> algorithms, but you will find even less people capable of creating 
>>> efficient
>>> algorithms than you will find capable of coding correctly.
>>>       
>> That is true, that is why we see a lot more microoptimizations than 
>> algorithmic progress.
>>     
>
> Also, algorithmic research is very little rewarding. You can work for
> months or years thinking you found the nice algo for the job, then
> finally discover a limitation you did not expect and throw that amount
> of work to the bin in a few minutes.
>   

You don't need to prove that P == NP to improve things.  Most 
improvements are in adding new APIs and data structures to keep the 
inner loops working on more data.  And of course scalability work to 
keep data local to a processing core.

It won't win you a Nobel prize, but you'll be able to measure a few 
percent improvement on a real-life workload instead of 10 cycles on a 
microbenchmark.

>   
>> But if you want a fast streaming filesystem you choose XFS over ext3, 
>> even though the latter is much smaller and easier to optimize.  If you 
>> write a network server you choose epoll() instead of trying to optimize 
>> select() somehow.
>>     
>
> That's interesting that you cite epoll() vs select(). I measured the
> break-even point around 1000 FDs. Below, select() is faster. Above,
> epoll() is faster. On small number of entries (less than 100), a select
> based proxy can be 20-30% faster than the same one running on epoll()
> because select() while dumber is cheaper to set up.
>   

[IIRC epoll() setup is done outside the loop, just once]

The small proxy probably doesn't have a performance problem, while 10K 
connection servers do.
>> Unless you are I/O bound, which is usually the case when you have 2GHz 
>> cpus driving 200Hz disks.
>>     
>
> That's true when you seek a lot. When you manage to mostly perform sequential
> reads (such as what you do when processing large files such as logs), you can
> easily achieve 80 MB/s, which is 20000 pages/s, or 100 times faster.
>
>   

Right, and this was achieved by having very good batching in the bio layer.

>> Can you give an example of a 2- or 3- fold factor on an end-user 
>> workload achieved by microopts?
>>     
>
> Oh there are many primitives which are generally optimized in assembly for
> this reason. What randomly comes to my mind :
>   - graphics libraries. Saving 1 cycle per pixel in a rectangle drawing
>     primitive can have an important impact in animated graphics for
>     instance.
>
>   - video/audio and generally multimedia code. I remember a specially
>     written version of mpg123 about 10 years ago, which was optimized
>     for i486 and which was the only one able to run on a 486 without
>     skipping.
>
>   - crypto code. It's common to find CPU-specific DES or AES functions.
>     Take a look at John The Ripper. I don't know if it still exists,
>     but there was an Alpha-optimized DES function which was something
>     like 5 times faster than the generic C one. It changes a lot of
>     things when you have 1 day to check your users passwords.
>   

These are indeed cases where the inner loop is executed millions times 
per second.  Of course it is perfectly reasonable to assembly code these.

I'm talking about regular C code.  Most C code is decision taking and 
pointer chasing, which is why traditional microopts don't help much.


> I also wrote a netfilter log analyzer which parses 300000 lines per
> second on my 1.7 GHz notebook. That's 5600 cycles to read a full
> line, lookup the field names, extract the values, parse them (atoi,
> aton) save them in a structure, apply a filter, insert the result
> in a tree containing up to 12 millions of them, and dump a report
> of the counts by any creteria. That saved me a lot of time working
> on log analysis. But to achieve such a speed, I had to optimize at
> every level, including rewriting a faster atoi() equivalent, a
> faster aton() equivalent (with no multiplies), and playing with
> likely/unlikely a lot. The code slowly improved from about 75k
> lines/s to 300k lines/s with no algorithmic change. Just by the
> way of careful code placement and ordering.
>   

Curious:  wasn't the time dominated by the tree code? 12M nodes is 24 
levels, and probably unpredictable to the processor unless the data is 
very regular.

> In fact, you could say that micro-optimizations are not important
> if you are doing them in a crappy environment where the fast path
> is already wasted by a big dirty function. But when you have the
> ability to master all the environment, every single cycle counts
> because there's almost no waste.
>
>   

That only works if the environment is very small.  A large scale project 
needs abstractions, otherwise you spend all your time re-learning all 
the details.

> I find it essential not to be the first one bringing crap somewhere
> and serving as an excuse for others not to care about their code.
> If everyone cares, you can still produce very good software, and
> that's what I care about.

We just disagree about the methods.

-- 
error compiling committee.c: too many arguments to function

--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@...r.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/

Powered by blists - more mailing lists