OSDev.org

The Place to Start for Operating System Developers
It is currently Thu Mar 28, 2024 7:12 pm

All times are UTC - 6 hours




Post new topic Reply to topic  [ 38 posts ]  Go to page 1, 2, 3  Next
Author Message
 Post subject: Optimization
PostPosted: Tue Oct 18, 2022 1:27 pm 
Offline
Member
Member

Joined: Fri Feb 11, 2022 4:55 am
Posts: 435
Location: behind the keyboard
Can you guys propose some types of optimizations to increase the performance of any program :)


Top
 Profile  
 
 Post subject: Re: Optimization
PostPosted: Tue Oct 18, 2022 3:05 pm 
Offline
Member
Member

Joined: Mon Feb 02, 2015 7:11 pm
Posts: 898
Sure... remove code. The less code you have the faster your program will be.

_________________
https://github.com/kiznit/rainbow-os


Top
 Profile  
 
 Post subject: Re: Optimization
PostPosted: Tue Oct 18, 2022 9:22 pm 
Offline
Member
Member

Joined: Wed Aug 30, 2017 8:24 am
Posts: 1593
kzinti wrote:
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.
devc1 wrote:
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.

_________________
Carpe diem!


Top
 Profile  
 
 Post subject: Re: Optimization
PostPosted: Wed Oct 19, 2022 12:25 am 
Offline
Member
Member
User avatar

Joined: Thu May 12, 2011 7:24 pm
Posts: 89
nullplan wrote:
kzinti wrote:
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.

_________________
Those who understand Unix are doomed to copy it, poorly.


Top
 Profile  
 
 Post subject: Re: Optimization
PostPosted: Wed Oct 19, 2022 1:37 am 
Offline
Member
Member
User avatar

Joined: Sat Mar 31, 2012 3:07 am
Posts: 4591
Location: Chichester, UK
kzinti wrote:
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.


Top
 Profile  
 
 Post subject: Re: Optimization
PostPosted: Wed Oct 19, 2022 4:16 am 
Offline
Member
Member

Joined: Mon Feb 02, 2015 7:11 pm
Posts: 898
iansjack wrote:
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.

_________________
https://github.com/kiznit/rainbow-os


Top
 Profile  
 
 Post subject: Re: Optimization
PostPosted: Wed Oct 19, 2022 6:26 am 
Offline
Member
Member

Joined: Fri Feb 11, 2022 4:55 am
Posts: 435
Location: behind the keyboard
How do we iterrate on a large array of linked lists faster ?


Top
 Profile  
 
 Post subject: Re: Optimization
PostPosted: Wed Oct 19, 2022 6:37 am 
Offline
Member
Member
User avatar

Joined: Sat Mar 31, 2012 3:07 am
Posts: 4591
Location: Chichester, UK
kzinti wrote:
iansjack wrote:
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.


Top
 Profile  
 
 Post subject: Re: Optimization
PostPosted: Wed Oct 19, 2022 6:41 am 
Offline
Member
Member
User avatar

Joined: Sat Mar 31, 2012 3:07 am
Posts: 4591
Location: Chichester, UK
devc1 wrote:
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.


Top
 Profile  
 
 Post subject: Re: Optimization
PostPosted: Wed Oct 19, 2022 10:22 am 
Offline
Member
Member

Joined: Mon Feb 02, 2015 7:11 pm
Posts: 898
iansjack wrote:
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.

_________________
https://github.com/kiznit/rainbow-os


Top
 Profile  
 
 Post subject: Re: Optimization
PostPosted: Wed Oct 19, 2022 11:07 am 
Offline
Member
Member
User avatar

Joined: Sat Mar 31, 2012 3:07 am
Posts: 4591
Location: Chichester, UK
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.


Top
 Profile  
 
 Post subject: Re: Optimization
PostPosted: Wed Oct 19, 2022 11:54 am 
Offline
Member
Member

Joined: Mon Mar 25, 2013 7:01 pm
Posts: 5100
devc1 wrote:
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.


Top
 Profile  
 
 Post subject: Re: Optimization
PostPosted: Wed Oct 19, 2022 12:01 pm 
Offline
Member
Member

Joined: Fri Feb 11, 2022 4:55 am
Posts: 435
Location: behind the keyboard
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 ?


Last edited by devc1 on Wed Oct 19, 2022 12:10 pm, edited 2 times in total.

Top
 Profile  
 
 Post subject: Re: Optimization
PostPosted: Wed Oct 19, 2022 12:03 pm 
Offline
Member
Member

Joined: Fri Feb 11, 2022 4:55 am
Posts: 435
Location: behind the keyboard
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.


Top
 Profile  
 
 Post subject: Re: Optimization
PostPosted: Wed Oct 19, 2022 12:56 pm 
Offline
Member
Member

Joined: Mon Mar 25, 2013 7:01 pm
Posts: 5100
devc1 wrote:
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...)

devc1 wrote:
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.

devc1 wrote:
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?

devc1 wrote:
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.


Top
 Profile  
 
Display posts from previous:  Sort by  
Post new topic Reply to topic  [ 38 posts ]  Go to page 1, 2, 3  Next

All times are UTC - 6 hours


Who is online

Users browsing this forum: Bing [Bot], DotBot [Bot] and 64 guests


You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot post attachments in this forum

Search for:
Jump to:  
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group