Tuesday, May 31, 2005
What will be the next revolution in task execution?
Task execution and scheduling concepts came into limelight with the advent of multiprocessing Operating Systems. Unix made processes popular and then SUN made threads popular (the defacto now for task execution). What do you think the next wave will be?
Monday, May 30, 2005
[RFC] How many addresses can you take in C?
Well, I decided that I would post a question and ask for comments. The question is
In the programming language "C", how many times can you take the address of a variable v? So if v is a variable can I use &v, &&v, &&&v, etc? What is the limit to taking addresses?
I think I know the answer and it seems straight forward. Once, I get comments, I will try and illustrate the answer
In the programming language "C", how many times can you take the address of a variable v? So if v is a variable can I use &v, &&v, &&&v, etc? What is the limit to taking addresses?
I think I know the answer and it seems straight forward. Once, I get comments, I will try and illustrate the answer
Thursday, May 26, 2005
The Rule of Three or More
I remember learning as a kid, that if a number is divisible by three, then the sum of the digits must be divisible by three. Ever wondered how this rule works and how someone must have discovered it. The proof is really simple and franckly quite amazing. I have been wanting to share it for a long long time now.
Well, lets use this theorem with b=3. Lets take a number 'a' for which we need to figure out divisibility by 3. Lets take an example, say 1021. We can rewrite 1021 as 1x1000+0x100+2x10+1.
Now try using mod 3 for the numbers above (Use Fermat's Little Theorem if you have to  more on that in the blogs to follow).
Any power of 10 mod 3 is 1. 10 mod 3 = 1, 100 mod 3 = 10 mod 3 x 10 mod 3 = 1 x 1 = 1. Thats a simple proof  right?
Now, in our example
1021 mod 3 = 1 mod 3 + 0 mod 3 + 2 mod 3 + 1 mod 3 (remember all powers of 10 mod 3 is 1, hence we are reduced to multiplying the digits with 1)
This is further equal to (1+0+2+1) mod 3 == 1 (Thanks Vinay!).
The proof should be trivial to extend to any generic number, by splitting it into powers of 10 and the digits and summing them up. All powers of 10 mod 3 yeild one, hence we need to use only the sum of the digits mod 3.
Well, lets use this theorem with b=3. Lets take a number 'a' for which we need to figure out divisibility by 3. Lets take an example, say 1021. We can rewrite 1021 as 1x1000+0x100+2x10+1.
Now try using mod 3 for the numbers above (Use Fermat's Little Theorem if you have to  more on that in the blogs to follow).
Any power of 10 mod 3 is 1. 10 mod 3 = 1, 100 mod 3 = 10 mod 3 x 10 mod 3 = 1 x 1 = 1. Thats a simple proof  right?
Now, in our example
1021 mod 3 = 1 mod 3 + 0 mod 3 + 2 mod 3 + 1 mod 3 (remember all powers of 10 mod 3 is 1, hence we are reduced to multiplying the digits with 1)
This is further equal to (1+0+2+1) mod 3 == 1 (Thanks Vinay!).
The proof should be trivial to extend to any generic number, by splitting it into powers of 10 and the digits and summing them up. All powers of 10 mod 3 yeild one, hence we need to use only the sum of the digits mod 3.
Tuesday, May 24, 2005
If you use a shell
I am sure many of you who use a shell like the bash shell or the korn shell or any other shell for that matter must be power users of it by now. I will probably blog on some fun shell techniques, like the one in this blog.
Korn shell comes with a variant of the "cd" command that very few people are aware of. It is very useful for people who tend to have symmetrical directory hierarchies
Lets assume that you are in a directory structure as shown below
(1) /home/user/programming/drivers/source/cxx
and want to change directories to
(2) /home/user/programming/user_mode/source/cxx
Well, in KSH you can say
"cd drivers user_mode" and it will change from (1) to (2). I love this feature and miss it in the BASH shell, so I wrote my own wrapper (that's why I love *NIX)
function cd
{
case $# in
1) builtin cd $1
return ;;
2) builtin cd ${PWD/$1/$2}
return ;;
*) builtin cd $*
return ;;
esac
}
In fact this version is slightly different from the KSH one, can you spot the difference?
Let me know if you do, I will post your name(s) on this blog
Korn shell comes with a variant of the "cd" command that very few people are aware of. It is very useful for people who tend to have symmetrical directory hierarchies
Lets assume that you are in a directory structure as shown below
(1) /home/user/programming/drivers/source/cxx
and want to change directories to
(2) /home/user/programming/user_mode/source/cxx
Well, in KSH you can say
"cd drivers user_mode" and it will change from (1) to (2). I love this feature and miss it in the BASH shell, so I wrote my own wrapper (that's why I love *NIX)
function cd
{
case $# in
1) builtin cd $1
return ;;
2) builtin cd ${PWD/$1/$2}
return ;;
*) builtin cd $*
return ;;
esac
}
In fact this version is slightly different from the KSH one, can you spot the difference?
Let me know if you do, I will post your name(s) on this blog
Saturday, May 21, 2005
Welcome Sathya to the world of blogging
For all of us who know Sathya N J, lets welcome him to the world of blogging
His first blog is at 360 Yahoo BLOG. I am glad I invited him to 360 yahoo.
His first blog is at 360 Yahoo BLOG. I am glad I invited him to 360 yahoo.
Thought for the day
I have been thinking about security for a while. I have come up with a probable law, but I am not sure if it is already well know. Anyway, here goes.
"The More free memory you have on your system, the more your system will be vulnerable to security risks"
Stated Mathematically
Security risk is directly proportional to the free memory on your system.
Do you think it makes sense?
I will explain my theory in detail in another posting, sometime later.
"The More free memory you have on your system, the more your system will be vulnerable to security risks"
Balbir Singh
Stated Mathematically
Security risk is directly proportional to the free memory on your system.
Do you think it makes sense?
I will explain my theory in detail in another posting, sometime later.
Friday, May 20, 2005
Can my blog be audible  part II
I had asked in Can my blog be audible if I can make my blog audible at run time. Well I am glad to say that a 10MB plugin in the Opera Browser enables me to achieve what I want.
After downloading the voice enabler, click on the text and type "v".
Cool! right?
After downloading the voice enabler, click on the text and type "v".
Cool! right?
Thursday, May 19, 2005
Interesting article to read
Monday, May 16, 2005
Intermediate Trees
Well, I have Intermediate Tree (IT) output from my tiger compiler. I received some help with the IT generation, but the text output is just not readable. So, what I did was generated a graphical representation using graphviz.
The most difficult thing about IT generation is following static links. I am going to show you the tree and the code that generates it.
and here is the tree
The tree on the right shows the main code
Can you guess what tree the following code will generate
Well, the tree could take up a whole room, so here is the
condensed version
If you find too many long left/right subtrees, well they are due to static links. The language is tiger, see Andrew Appel's Home Page for more details
WARNING: The IT have not been checked for correctness, I can only hope they are correct.
The most difficult thing about IT generation is following static links. I am going to show you the tree and the code that generates it.
/* define a recursive function */
let
/* calculate n! */
function nfactor(n: int): int =
if n = 0
then 1
else n * nfactor(n1)
in
nfactor(10)
end
and here is the tree
The tree on the right shows the main code
Can you guess what tree the following code will generate
let
type any = {any : int}
var buffer := getchar()
function readint(any: any) : int =
let var i := 0
function isdigit(s : string) : int =
ord(buffer)>=ord("0") &
ord(buffer)<=ord("9")
function skipto() =
while buffer=" "  buffer="\n"
do buffer := getchar()
in skipto();
any.any := isdigit(buffer);
while isdigit(buffer)
do (i := i*10+ord(buffer)ord("0");
buffer := getchar());
i
end
type list = {first: int, rest: list}
function readlist() : list =
let var any := any{any=0}
var i := readint(any)
in if any.any
then list{first=i,rest=readlist()}
else nil
end
function merge(a: list, b: list) : list =
if a=nil then b
else if b=nil then a
else if a.first < b.first
then
list{first=a.first,rest=merge(a.rest,b)}
else
list{first=b.first,rest=merge(a,b.rest)}
function printint(i: int) =
let function f(i:int) = if i>0
then (f(i/10);
print(chr(ii/10*10+ord("0"))))
in if i<0 then (print(""); f(i))
else if i>0 then f(i)
else print("0")
end
function printlist(l: list) =
if l=nil then print("\n")
else (printint(l.first); print(" ");
printlist(l.rest))
var list1 := readlist()
var list2 := (buffer:=getchar();
readlist())
/* BODY OF MAIN PROGRAM */
in printlist(merge(list1,list2))
end
Well, the tree could take up a whole room, so here is the
condensed version
If you find too many long left/right subtrees, well they are due to static links. The language is tiger, see Andrew Appel's Home Page for more details
WARNING: The IT have not been checked for correctness, I can only hope they are correct.
Blog(net)working
I am really happy about the fact that the number of blogs are growing very rapidly these days. The December 2004 communications of ACM has a great article on the distribution of blogs worldwide. That also means that many of my friends and inturn their friends have blogs. Almost all of us maintain a set of links on the sidebar linking blogs of our friends. Even though I have not directly spoken to them for sometime now, I get to know what they are upto through their blogs. I like of think of it as Blogworking, instead of networking we have Blogworking. Get it?
Lets keep up the Blogworking.
Lets keep up the Blogworking.
Friday, May 13, 2005
Wondering What I Have Been Upto?
I have not been updating my blog as frequently as I used to, of late. I have a good excuse, well I am busy with something and I am also working on finishing the tiger implementation. I have learnt many interesting things and I cannot wait to share them here.
Thursday, May 12, 2005
Monday, May 09, 2005
Can my blog be audible?
I am exploring techniques to make my blog audible, yes audible!
Unfortunately, I do not own the blog server and hence do not have access to any technology on the server side. I will be forced to implement something at the client end. Does anybody know of a good technology to help me make my blog audible?
Let me know if you do or any suggestions you have
Unfortunately, I do not own the blog server and hence do not have access to any technology on the server side. I will be forced to implement something at the client end. Does anybody know of a good technology to help me make my blog audible?
Let me know if you do or any suggestions you have
Thursday, May 05, 2005
Return Addresses
Andrew Appel states that return addresses were earlier pushed on the stack by the function call instruction. Data shows that it is faster and easier to pass the return addresses in a register. This has two advantages
 It keeps the memory traffic down
 It avoids building in any particular stack discipline into the machine
This is certainly true for MIPS, ARM, etc. For the Intel IA32 platform see Notes on Translating ThreeAddress Code to Assembly Code for the X86.
The return address is still stored on stack. Generally the ENTER, LEAVE and RET instructions are used for stack manipulation. Gcc uses CALL, LEAVE and RET.
Tuesday, May 03, 2005
The Composite Pattern
The Design Patterns (Gang of Four) book explains the composite pattern. See Composite Pattern
One example of a composite pattern is a file in a filesystem/directory hierarchy. The figure below shows a probable implementation of a filesystem hierarchy using the composite pattern
Sunday, May 01, 2005
First Analysis of Swap Space
When I was learning to configure my first Dynix/Ptx system, I was told by a senior team member to ensure that the swap is at least twice the memory size. I asked him what was the logic behind that, he said, it was a rule of thumb. In the time to come, I would learn the some reasoning behind it. I would at this point recommend “Modern Operating Systems, by Andrew S. Tanenbaum”. He uses Don Knuth’s Fifty Percent Rule as the basis for his analysis. Let me explain the Fifty Percent Rule first
The simple explanation of the rule follows. In the state of equilibrium
This tells us that the ratio of holes to allocated blocks is fifty percent.
In the state of equilibrium there are half as many holes as total allocated blocks. A hole is referred to as a available memory (free memory). If the total allocated memory in blocks is n then the number of holes is n/2.
The total available blocks is 3n/2 and available blocks is n/2. The ratio of free memory to total available memory (assuming block sizes are equal) comes to 1/3. So if you have 256MB of RAM on your system and want it to be available free for the next task you want to run, then you must allocate a swap size of 512MB, so that the ratio of 1/3 is held.
There are of course complications to this simple rule or calculation that I explained above. I will try and explain some of those complexities in the next series of swapping articles.
The simple explanation of the rule follows. In the state of equilibrium
 Half the number of memory operations are allocations, the other half is freeing
 For the half that is freeing, half of those operations result in holes being merged (contiguous ones)
This tells us that the ratio of holes to allocated blocks is fifty percent.
In the state of equilibrium there are half as many holes as total allocated blocks. A hole is referred to as a available memory (free memory). If the total allocated memory in blocks is n then the number of holes is n/2.
The total available blocks is 3n/2 and available blocks is n/2. The ratio of free memory to total available memory (assuming block sizes are equal) comes to 1/3. So if you have 256MB of RAM on your system and want it to be available free for the next task you want to run, then you must allocate a swap size of 512MB, so that the ratio of 1/3 is held.
There are of course complications to this simple rule or calculation that I explained above. I will try and explain some of those complexities in the next series of swapping articles.
Subscribe to:
Posts (Atom)
Dynamic programming for the binomial coefficient
More fun things, this time with some visualisation of what happens when memoisation is used and what happens when we don't. I don'...

I found this in the latest C++ draft specification Type names obey exactly the same scope rules as other names.In particular, type names de...

I've been reading up on Fast Fourier Transform (FFT) from several books on algorithms that I have, TCLR, Tamassia, Sahni, Numerical Rec...

Michael Ellerman has a great blog with all the technical details. There was a lot of work, brain storming and discussions involved. Check o...