Optimization

[devc1]

Can you guys propose some types of optimizations to increase the performance of any program

[kzinti]

Sure... remove code. The less code you have the faster your program will be.

[nullplan]

Sure... remove code. The less code you have the faster your program will be.

Seconded. The fastest code is the code that doesn't run. Also the smallest.

Can you guys propose some types of optimizations to increase the performance of any program

There is no silver bullet. Each program is different. My advice is to first build the program to solve your problem, then check to see if performance is sufficient for your (customer's) needs. If so, awesome, you are done.

If not: profiling, profiling, profiling. Find out where your application is spending its time, and optimize whatever you can there. Try better algorithms. Try better solutions for subproblems. Always be measuring the impact of your changes.

[Minoto]

Sure... remove code. The less code you have the faster your program will be.

Seconded. The fastest code is the code that doesn't run. Also the smallest.

Old joke, paraphrased: All programs can be shortened by at least one instruction, and all programs contain at least one bug. Therefore, every program can be optimized down to one instruction which doesn't work.

[iansjack]

Sure... remove code. The less code you have the faster your program will be.

That's obviously false.

For example, write a program to print a table of squares from 1 to 10 - the fastest program will be much longer than the shortest one.

[kzinti]

For example, write a program to print a table of squares from 1 to 10 - the fastest program will be much longer than the shortest one.

Remove the code to print the squares and it will be even faster.

[devc1]

How do we iterrate on a large array of linked lists faster ?

[iansjack]

For example, write a program to print a table of squares from 1 to 10 - the fastest program will be much longer than the shortest one.

Remove the code to print the squares and it will be even faster.

But then it won’t satisfy the condition of being a program to print a table of squares.

It’s trivial to say that you can reduce the run time of any program to 0 by removing all the code. But it’s not very useful.

[iansjack]

How do we iterrate on a large array of linked lists faster ?

That’s too general a question.

The too general answer is that you rewrite the data structures and/or algorithms to be more efficient. This probably won’t produce the smallest program. Quicksort probably involves more code than bubble sort but it is, in the general case, likely to be faster.

[kzinti]

It’s trivial to say that you can reduce the run time of any program to 0 by removing all the code. But it’s not very useful.

Indeed, I think some of the sarcasm in my initial reply got lost along the way. Re-read it in the context of the original question asking for a generic optimization solution to all programs. The only one I could come up with was to delete code. I was trying to be funny.

That said I do believe that less code in general is a good thing. But code should not be reduced in size while sacrificing other aspects of the code/program such as readability, performance and so on. It is always a balancing act.

The right answer to the OP question is of course to identify the bottlenecks in your code (presumably by profiling it) and only address those bottlenecks. Your example of quicksort being faster than bubble sort is an example where more code is called for. There are of course many others.

[iansjack]

Probably the best example of where (a lot) more code speeds a program up dramatically is when reading from a block device; an example that we have seen discussed here recently.

Another answer to the question is “don’t reinvent what others have done better”. In other words, use well-writeten libraries and don’t fall into the trap of thinking that the answer is to write everything in assembly language. In the end there’s no substitute for experience (and measurement) when optimising code.

[Octocontrabass]

How do we iterrate on a large array of linked lists faster ?

A lot of optimization is choosing the appropriate data structure. For example, if you frequently need to search a linked list for specific items, your best optimization might be replacing the linked list with a self-balancing binary tree.

[devc1]

Do you mean by the binary tree some structures like page tables ?

I guess the quicksort algorithm will be usefull when creating linked lists with an ID for each item, so you can use this algorithm to get the Item from the ID faster ?

[devc1]

I use an optimization to find free and allocated items is that on each linked list I create a bitmap where each bit represents an allocated entry/item. I use the bsf (Bit Scan Forward) to find an allocated item, to find a free item I just reverse the bits using the not instruction then bsf.

I may create multiple bitmaps to fit the list in a page where I can benefit from the tlb cache, and I make sure that the list is page aligned.

[Octocontrabass]

Do you mean by the binary tree some structures like page tables ?

Page tables are a type of tree data structure, but they're not a binary tree. (I don't actually know offhand what type of tree they are...)

I guess the quicksort algorithm will be usefull when creating linked lists with an ID for each item, so you can use this algorithm to get the Item from the ID faster ?

If you're primarily using the list to look up the item using the ID, then you probably shouldn't create a linked list in the first place. If the data is static, you might create an array sorted by ID and use a binary search to find the item. If the data is dynamic, you might create a self-balancing binary tree.

I use an optimization to find free and allocated items is that on each linked list I create a bitmap where each bit represents an allocated entry/item.

Why do you need to search for both free and allocated items?

I use the bsf (Bit Scan Forward) to find an allocated item, to find a free item I just reverse the bits using the not instruction then bsf.

You shouldn't worry about this kind of optimization until you have chosen an appropriate data structure. It sounds like a linked list is not the appropriate data structure.