OSDev.org

The Place to Start for Operating System Developers
It is currently Tue Mar 19, 2024 2:13 am

All times are UTC - 6 hours




Post new topic Reply to topic  [ 8 posts ] 
Author Message
 Post subject: Optimization to get a number in a range from a given value
PostPosted: Mon May 16, 2016 2:30 pm 
Offline
Member
Member
User avatar

Joined: Tue Mar 06, 2007 11:17 am
Posts: 1225
I need an optimized way to limit a value and adjust it to get the offset that would correspond to it.

If I have a very big buffer in one place, but I want to copy only a tiny buffer, I still know the offset that would correspond if I want to access it (for example, if I want to read only 1 or 2 sectors of a FAT12 table at a time).



A slow way would be like this:
Code:
var originalValue=24531;

//The following will result in 467,
//but will be uselessly slow:
///
while(originalValue>=512)
{
  originalValue-=512;
}




And it seems that a way would be to use an AND with a mask set to all 1's for the size that corresponds to the size of the partial buffer. For example, for a 512-byte partial buffer, it would just take:

Code:
var originalValue=24531;

//The following will result in 467, with base address of 0:
///
originalValue&=parseInt("111111111", 2);   //AND with 511 to get a value between 0 to 511



___________________________________________________________________________
___________________________________________________________________________
___________________________________________________________________________
___________________________________________________________________________
(FAT) Reading 2 File Allocation Table Sectors At a Time Instead of 1

It seems to be a trick similar to that from the Graphics Programming Black Book, which talks about reading and searching through partially-loaded files with resume.

It looks like some Cluster Numbers when stored on disk traverse and go beyond a single sector, specifically those that happen to start at byte 511 of a 512-byte sector. Each cluster for FAT12 uses 2 bytes, so it would end up with 1 byte in each sector, the first at the very end of the first sector (offset 511) and the second at the very start of the second/next sector (offset 0).

So, as long as we have already adjusted and know the actual offset of the cluster into the FAT, we will always avoid that division of a cluster value between 2 sectors if we simply read 2 FAT sectors instead of 1. Then the partial value will now always be available with this trick.

The code to handle it will also be smaller and we will just need a 1024-byte buffer instead of a 512-byte one.

It seems to be very good trick to be able to read partial values, be able to resume them, and avoid reading the whole data set (the whole FAT table).


___________________________________________________________________________
___________________________________________________________________________
___________________________________________________________________________
___________________________________________________________________________
Getting Lowest and Highest Number from Bigger Value?

Now the question is, how could I also get an offset only between N and M, for example, only between 1-511 or only between 127-511 instead of the typical one 0-511 where only the highest value matters but not the lowest?

_________________
Live PC 1: Image Live PC 2: Image

YouTube:
http://youtube.com/@AltComp126/streams
http://youtube.com/@proyectos/streams

http://master.dl.sourceforge.net/projec ... 7z?viasf=1


Top
 Profile  
 
 Post subject: Re: Optimization to get a number in a range from a given val
PostPosted: Mon May 16, 2016 2:47 pm 
Offline
Member
Member
User avatar

Joined: Wed Jan 06, 2010 7:07 pm
Posts: 792
The bitwise-and trick is a special case of modular arithmetic, where the modulus is a power of two. In general, you can get X into the range [0,N) with X % N.

If I understand you correctly, your [N,M) range can also be seen as N+[0,M-N), so you could use (X - N) % M + N.

_________________
[www.abubalay.com]


Top
 Profile  
 
 Post subject: Re: Optimization to get a number in a range from a given val
PostPosted: Tue May 17, 2016 10:39 am 
Offline
Member
Member
User avatar

Joined: Fri Oct 27, 2006 9:42 am
Posts: 1925
Location: Athens, GA, USA
Rusky wrote:
The bitwise-and trick is a special case of modular arithmetic, where the modulus is a power of two. In general, you can get X into the range [0,N) with X % N.

If I understand you correctly, your [N,M) range can also be seen as N+[0,M-N), so you could use (X - N) % M + N.


While this is true, the trick is still one that could be of use, as it is both easy to code and faster than the modulo operator (which uses integer division to get the modulus, or rather, the remainder). OTOH, it only us usable for powers of two (though that should be the case for most values you would use), and the intent is less clear than using the modulo operator would be. It would probably be premature optimization to commit to it right at the start.

On the gripping hand, I would expect a good C compiler to recognize the special case of a modulo by a constant power of two and perform the optimization automagically (just as I would expect it to replace a multiply or divide with a shift when appropriate), so it is probably a moot point from a performance standpoint.

_________________
Rev. First Speaker Schol-R-LEA;2 LCF ELF JAM POEE KoR KCO PPWMTF
Ordo OS Project
Lisp programmers tend to seem very odd to outsiders, just like anyone else who has had a religious experience they can't quite explain to others.


Top
 Profile  
 
 Post subject: Re: Optimization to get a number in a range from a given val
PostPosted: Tue May 17, 2016 1:14 pm 
Offline
Member
Member

Joined: Sat Mar 01, 2014 2:59 pm
Posts: 1146
Schol-R-LEA wrote:
On the gripping hand, I would expect a good C compiler to recognize the special case of a modulo by a constant power of two and perform the optimization automagically (just as I would expect it to replace a multiply or divide with a shift when appropriate), so it is probably a moot point from a performance standpoint.
I would be interested to see if that is actually the case though, as I usually work on the assumption that the compiler doesn't perform such specific optimizations.

_________________
When you start writing an OS you do the minimum possible to get the x86 processor in a usable state, then you try to get as far away from it as possible.

Syntax checkup:
Wrong: OS's, IRQ's, zero'ing
Right: OSes, IRQs, zeroing


Top
 Profile  
 
 Post subject: Re: Optimization to get a number in a range from a given val
PostPosted: Tue May 17, 2016 1:56 pm 
Offline
Member
Member

Joined: Mon Mar 25, 2013 7:01 pm
Posts: 5069
onlyonemac wrote:
I would be interested to see if that is actually the case though, as I usually work on the assumption that the compiler doesn't perform such specific optimizations.

GCC does. Here's a function that does nothing but return a value modulo 512 compiled for i386:
Code:
mov    eax,DWORD PTR [esp+0x4]
and    eax,0x1ff
ret

Here's the same function for m68k:
Code:
linkw %fp,#0
movel %fp@(8),%d0
andil #511,%d0
unlk %fp
rts

And powerpc:
Code:
clrlwi  r3,r3,23
blr

I tried -O0, but it still generated the same optimized code (with prologue and epilogue fluff). I expect you'll see similar results with other optimizing compilers.


Top
 Profile  
 
 Post subject: Re: Optimization to get a number in a range from a given val
PostPosted: Wed May 18, 2016 2:47 pm 
Offline
Member
Member
User avatar

Joined: Fri Oct 27, 2006 9:42 am
Posts: 1925
Location: Athens, GA, USA
Thank you, Octocontrabass, I should have thought to check before posting that myself. I didn't think I would need to, though; like constant folding and tail-call optimization, power-of-two optimizations for integer arithmetic are pretty well established, and unlike TCO, it is hard to see any possible downsides to it (TCO folds the stack, making tracing it in debugging impossible without adding large data structures and expensive operations while losing most of the advantages of TCO). It would come well before more complicated techniques such as even basic register painting in the list of things a compiler writer would implement, and would be feasible even with a fairly simple recursive-descent direct-emit compiler, which is problematic even for something as simple as constant folding (which could require a peephole pass over the output of such a compiler, since a basic aspect of RDDE parsers is that they don't need to keep any information about previous statements aside from the symbol table).

_________________
Rev. First Speaker Schol-R-LEA;2 LCF ELF JAM POEE KoR KCO PPWMTF
Ordo OS Project
Lisp programmers tend to seem very odd to outsiders, just like anyone else who has had a religious experience they can't quite explain to others.


Top
 Profile  
 
 Post subject: Re: Optimization to get a number in a range from a given val
PostPosted: Wed May 18, 2016 3:19 pm 
Offline
Member
Member
User avatar

Joined: Fri Oct 27, 2006 9:42 am
Posts: 1925
Location: Athens, GA, USA
Oh, and just to show that TCO is simple enough to do (sometimes) with an RDDE parser that emits assembly code, here's how it works.

1) at the beginning of every function, emit a secondary entry point label right after the activation frame is created.
2) Keep a table with the sizes of the activation records of every compiled function, and another with the sizes of their their parameter lists.

3) when parsing a return statement:
Code:
if the value is the return of another function, then it is a tail call
    if ((AR_size[callee] != NULL && PL_size[callee] != NULL) && (AR_size[callee] <= AR_size[caller]  &&  PL_size[callee] <= PL_size[callee]))
        replace the current arguments on the stack with the function call's arguments
        emit jump to the secondary entry point of the callee
    else
        emit normal function call
else
    not a tail call, emit value return as usual


While this is a simplified version, and It isn't a perfect solution (as it won't work if the callee hasn't been compiled yet or is an external call, or if the functions in question are type void), it will always work for simple tail recursion on a non-void function, and should work for many other cases as well. Still, the point is that yes, TCO is indeed a fairly basic technique that pretty much even the simplest compilers should be able to offer as an optional setting.

Now, just to prove the point, I'm going to try to add this to my own RDDE-based Suntiger Algol compiler, which admittedly I haven't touched in several years.

_________________
Rev. First Speaker Schol-R-LEA;2 LCF ELF JAM POEE KoR KCO PPWMTF
Ordo OS Project
Lisp programmers tend to seem very odd to outsiders, just like anyone else who has had a religious experience they can't quite explain to others.


Top
 Profile  
 
 Post subject: Re: Optimization to get a number in a range from a given val
PostPosted: Wed May 18, 2016 6:31 pm 
Offline
Member
Member
User avatar

Joined: Fri Oct 27, 2006 9:42 am
Posts: 1925
Location: Athens, GA, USA
sigh Me and my big fat mouth...

It seems I forgot a few things about that project, not the least of which being giving you a link to the Suntiger Algol GitHub repo. Most significantly, I forgot a) that I never did write the code to parse user-defined functions and function calls, and b) just what an unholy mess the code I wrote in the last three weeks of that course was. I think that taking some time to work on this might be a good idea, if only as a confidence-building warm-up exercise. So, the agenda for the rest of this week:

  • Fix the code for storing and retrieving labels, emitting code, and who knows what else,
  • add a symbol table subclass specifically for function names and signatures,
  • Write a simple function call parser,
  • write a simple function definition parser, and
  • extend those to handle tail call optimization
Mind you, I have long wanted to do this, and eventually want to re-write the parser itself to generate an AST (as I wanted to do from the first) instead of directly emitting code. Maybe this is a good thing, I know this is something I can do and it is probably worth doing if we ever get the CompilerDev wiki going.

_________________
Rev. First Speaker Schol-R-LEA;2 LCF ELF JAM POEE KoR KCO PPWMTF
Ordo OS Project
Lisp programmers tend to seem very odd to outsiders, just like anyone else who has had a religious experience they can't quite explain to others.


Top
 Profile  
 
Display posts from previous:  Sort by  
Post new topic Reply to topic  [ 8 posts ] 

All times are UTC - 6 hours


Who is online

Users browsing this forum: No registered users and 8 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