List:Ways to optimize a kernel!

[rdos]

typically ten times the nominal value if you're rdos

A function call is more than the x86 call instruction (and the x86 ret instruction). At least if you use a typical C-compiler.

[Solar]

q.e.d.

[Fanael]

It's not the compiler I am woried about, it's readability.

Fair then, but talking about readability in a thread explicitly regarding performance can be a bit confusing, mind you.

[gerryg400]

Isn't improving readability an acceptable optimisation ?

[Griwes]

It definitely is, as it makes maintaining the code way easier. Which is definitely an optimization, especially in some cases (maintaining unreadable algorithm, written in assembly a year before, anyone?).

[sandras]

As they say, first rule of optimization - don't do it.

[NickJohnson]

I would say the first rule of optimization is less "don't do it" and more "do it later". Never optimize code as you write it, but also don't design it so that it cannot be optimized in the future. It's easy to optimize a complete and working system, because a complete and working system will both give you realistic profiling data and will break more loudly/quickly if you cause a problem while optimizing.

[AndrewAPrice]

Premature optimisation also wastes time towards getting to working software.

Example 1:
I recently worked on a language parsing tool that dealt with 100,000 different strings. I was going to use a hash table (the language did not have one implemented in the standard library) to make it faster - but I would have to write my own. The hash table would make it run many magnitudes faster (I estimate in a couple of seconds) but would take a couple of days to implement. Instead I used a linked list - the program takes about 2 minutes to run. The reason I didn't optimize was because getting a working program immediately was more important than getting it to run fast (it was a tool I only use on my local computer so I'm prepared to wait for it to run). But I left room to replace the abstract data container type in the future incase I do want to optimize.

Example 2:
I'm working on an interpreter instead of a JIT compiler for my OS. Why? A JIT compiler would make the code execute significantly faster by would also take significantly longer to implement. I want to get a working bug-free OS before a fast OS.

Counter-Example:
If it doesn't add much development time on and it doesn't decrease code readability. E.g. using C#, I'm creating a lot of 16 byte objects. I knew from design that hundreds of thousands of these objects will be created per second. I decided to use a 'struct' instead of a 'class'. C# structs are allocated from the stack and passed by value (not by reference, unless you use the 'ref' modifier) and cleaning them up will never invoke the garbage collector.

[sandras]

I would say the first rule of optimization is less "don't do it" and more "do it later".

Maybe i should have quoted it, as those were not my own words, but I thought everybody here should realize that anyway. I do see the need to optimize at some point, as for example, on my own system I often experience lag. I mean my Linux installation, not the kernel I'm developing. ; ) Maybe I should have called it a warning, not a rule, cus that is what it serves as, really. If you do decide to optimize, then there's the "don't do it yet" rule. Which is pretty much what I think you mean by "do it later". So I guess we agree there.

Also, I think optimization is a very tricky thing. There are lots of things to consider, as there are many kind of machines. Not just different architectures - think of how many different configurations can, say, a x86 have, so this goes not only for the ones who think of portability. Think about different properties of different memory hierarchy levels - from L1 cache, if there even is one, down to hard disk, again, if there is one, or even network. How do you know making your kernel faster on one machine won't make it slower on the other, and vice versa. I think that having this in mind one should do general optimizations - those that apply for any kind of machine. For example, AFAIK, working with register sized integers is fastest on any machine, so you can spend a little time converting size in char's to size in int's and then save a lot of time looping in your memclr(). That's a very simple optimization, and the function code is still perfectly understandable. Also what can be a better optimization than not doing something at all?

Do some of you optimize for size? What do you think of it even if you don't optimize for it? I find it neat, that when you do that, you can always know how well you've optimized - you just measure it's size. Executable size is always the same, while performance depends on many variables. Besides, small size is always good for cache performance.

[sandras]

http://c2.com/cgi/wiki?RulesOfOptimization

Is what I'm talking about.

[NickJohnson]

I didn't realize there was an official list.

[qw]

Using special keywords such as 'register' and 'inline' ,etc

Just to add a little note: for optimization it is not wise to use "register". The compiler probably knows better than you do which variables should be "register" and which shouldn't. The "register" keyword is a left-over from times when optimization was in its infancy.

[OSwhatever]

I often find JTAG together with instruction recording capability through ETM or MIPI a good way to find out what is taking a lot of time in the kernel. Sampling is a good way to do it user space but in kernel space you often disable all interrupts. Well there are ways around it of course so that it works in kernel space as well with the interrupts disabled but this usually architecture dependent. The JTAG debugging programs usually comes with some kind of profiling functionality so that you can analyze what is taking time right down to every instruction.

[qw]

As a second note: "const" and "restrict" are very good for optimizing. They give the compiler the information it needs to generate the most efficient code, information that would otherwise be difficult to find out (especially because the compiler can check that you don't violate the "constness" of your objects).

[JamesM]

As a second note: "const" and "restrict" are very good for optimizing.

Restrict helps gcc auto-vectorize your code better.

And yet, you don't want that because you're unlikely to have SSE enabled in your kernel, right? (extra 512 bytes to context switch)