memory access times

[funkylunch]

i am not sure but I think it is quicker to acccess virtual memory
column by column as opposed to row by row.

Real memory displays opposite properties.

Can anyone explain why this is so? Or alternatively disprove this theory.

I am sorry that this is not directly related to c.

[ober]

In the tech board, most things are NOT related to C.

I googled and found this.
Not sure if it helps or not, but oh well.

[Salem]

Moved from C++ board...

Given arr[X][Y], the next memory location is accessed by arr[X][Y+1]
Two things happen here
1. adjacent memory locations are likely to be in the same virtual page
2. cache prediction logic will fetch incrementing addresses in advance of you needing them.

If on the other hand you have arr[X][Y] and arr[X+1][Y], these are far apart in memory.
Two things happen here
1. if the two locations are >= 1 page apart, you're in for a lot of VM page misses. The OS gets involved to reload swapped pages back in from disk. This is going to be hugely expensive.
2. The cache is useless at predicting such large jumps, and could well be flushed on each VM page miss.

> Real memory displays opposite properties.
Well if its neither cached nor paged, then it really makes no difference at all.

[funkylunch]

Thanks that is great. Are you sure it makes no difference to access times in terms of main memory if accessed row by row or column by column? I would like to check that using this simple visual c program which writes to memory row by row and column by column and times each way. All I need to do is make two programs from the code below: one which uses only physical memory and one which uses only virtual memory, could you show me how? thanks for your help, tim. The program might be c++, i am not sure... had to replace the brackets with @ and ~ to send this message.

<<MOD snipped code which failed to use code tags in a creative way>>

[Salem]

> had to replace the brackets with @ and ~ to send this message.
How creative of you!
Now go and read all the into posts which tell you how to use code tags properly!!!!
Jeez, where do you think all those nicely formatted posts come from.

Horrible code snipped from previous post

> simple visual c program
Since VC can't create programs which access real memory, the point is moot

[funkylunch]

ok,

sorry about the code. So can I re-write the program (rowcol.c, in my first thread which everyone was too scared to download) so it only uses virtual memory? isn't there a function called:

virtual alloc

thanks a lot, sorry again about the code.

t.

[funkylunch]

ok, so i need to post the code in the message somewhow. I looked in the FAQ but found nothing about posting visual c code. Please could someone tell me how to post the code as text here without gettng error messages?

[funkylunch]

oh, and what is moot?

[Waldo2k2]

I looked in the FAQ but found nothing about posting visual c code

you
are
stupid

you type [ followed by ] and put the word CODE in the middle. paste your code, then do the same as before only put /CODE in hte middle. It's in the FAQ...btw, visual C code is the same as C code is the same as any other code, just put it in code brackets.

[ober]

"moot" means you're asking a question that is pointless. Since VC can't create programs that can access memory directly, the answer to your question doesn't matter.

[funkylunch]

Right, so how can i modify this program so it only uses virtual memory? alternatively how else can i prove that

1. Accessing virtual memory column by column is slower than row by row.

2. These two accesing techniques make no difference to memory access time of main memory?

I have made a table in excel already and some graphs from the data. These basically show that column by column time is always longer. It also shows that column by column time actually decreases just before the system crashes! Some dude above has told me why, but I need to prove this theory mathmatically or by modifying the program and creating a new table & graphs. Windows won't let me have zero virtual memory. Any suggestions? I would be more than happy to supply the table & graphs if you want.

Yes, if you run the program below enough times it will freeze up your computer. Be careful, dont let it run any bigger than your total memory (physical + virtual)

here is the program, thanks for your time:

/*************************************************************************
RowCol.c

Experiment on row/column access to an array

*************************************************************************/

#include <stdio.h>
#include <conio.h>
#include <sys/timeb.h> 
#include <windows.h> 

void WaitUser();
unsigned long IntervalTimer();
int n;
/*
This commented out main() can be used to assess the accuracy of the IntervalTimer()
void main()
{				
	unsigned long msecs;
	unsigned long secs;

    printf("Enter interval time (secs): ");
    scanf("%i",&secs);

    n = 0;
	printf("\nn = %d\n",n);
	while(1){
        n++;
        IntervalTimer();
        Sleep(secs*1000);
        msecs = IntervalTimer();
		printf( "n = %d Time seconds:\t%ld   mseconds: \t%ld \n",n,msecs/60,msecs%60);

	}
}
*/

void main()
{
    char **Array;
    int n=0;
    int Row=16;
    int Column=16;
    int b;
    int r,c;
    int i;
    unsigned long RCTime, CRTime;

    for(i = 0; i < 12; i++){	
    	printf("\nArray size %d (%d x %d) ", Row*Column,Row, Column);
		Array=(char**)malloc(Row*sizeof(char*));
		for (b=0;b<Row;b++)
		    Array[b]=(char*)malloc(Column*sizeof(char));

		IntervalTimer();
	   
        for(r=0;r<Row;r++)
			for(c=0;c<Column;c++)
				Array[r][c]=1;
        RCTime = IntervalTimer();

		IntervalTimer();
		for(c=0;c<Column;c++)
	        for(r=0;r<Row;r++)
				Array[r][c]=1;
        CRTime = IntervalTimer();
	
    	printf(" RCTime(ms) %d CRTime(ms) %d ratio %f", 
            RCTime, CRTime, (float)CRTime/(float)RCTime);

		for (b=0;b<Row;b++)
            free(Array[b]);
        free(Array);

        Row *= 2; Column *= 2;
        printf(" Hit any key to continue");
        WaitUser();
	}
}

///////////////////////////////////////////////////////////
// IntervalTimer
// Measures a (single) simple time interval in msecs
// First call starts the interval, second call ends the 
// interval and returns the interval length in msecs
///////////////////////////////////////////////////////////
#define START 0
#define STOP 1
unsigned long IntervalTimer()
{
    static int StartStop = START;
    static struct _timeb tstructstart;
    static struct _timeb tstructstop;
    int msecs;
    unsigned long secs;

    if(StartStop == START){
        _ftime(&tstructstart);
        StartStop = STOP;
        return 0;
    }
    else{
        _ftime(&tstructstop);				
		msecs=tstructstop.millitm-tstructstart.millitm;
		secs=tstructstop.time-tstructstart.time;
		if (msecs<0) {msecs=1000+msecs;secs--;}
        StartStop = START;
        return secs*60 + msecs;
    }
}
    

void WaitUser()
{
    fflush(stdin);
    while(!kbhit());
    getch();
    //fflush(stdin);
}

[Brian]

Originally posted by funkylunch

void main()
...
fflush(stdin);

Where to begin...

[Salem]

> Yes, if you run the program below enough times it will freeze up your computer
heh, that's no surprise.
With all those Row *= 2; Column *= 2; you end up trying to allocate 4GB + 256K on the last iteration of the loop and that just isn't going to happen.

If your program stopped a couple of loops short of that, saying at 1GB max, then it might be more robust.

For starters, you need to make sure all your malloc calls return a valid pointer.

> return secs*60 + msecs;
Erm, what exactly are you trying to calculate here?
If you're trying to return the number of milliseconds, then it would be
return secs*1000 + msecs;

You need do more tests at each memory size - just one time is not going to cut it. There is a lot of background noise (interrupts, background processes etc) which will need to be averaged out.

RCTime = 0;
for ( j = 0 ; j < 10 ; j++ ) {
	IntervalTimer();
        for(r=0;r<Row;r++)
		for(c=0;c<Column;c++)
			Array[r][c]=1;
        RCTime += IntervalTimer();
}

And do the same for the CRTime as well.

[funkylunch]

Hi,

I think there is a way to run the whole program in virtual memory. Does anyone know how I would have to change the above code to acheive this?

I think it would involve the virtual alloc funtion, how would I implement this in the code?

thanks for all your help so far, has been great.

[funkylunch]

Salem,

I still cant unerstand why when you run this program it is always quicker to access the memory row by row. You said earlier that if it is neither cached or paged then it makes no difference. Are you sure about this?? Can you explain this difference?

cheers,