Freethought & Rationalism Archive

sophie · 07-11-2003, 05:29 AM

DNAunion, you missed the last point, which was clarified as virtual contiguity. Underline virtual contiguity.

It appears contiguous but in actual memory it may not necessarily be contiguous. However for your simple purposes of using arrays, you can well imagine it is contiguous.

Sorry I was talking above your head. For your purposes you are correct.

sophie · 07-11-2003, 05:36 AM

again DNAunion,

I selected one line of code to issue a trashing warning. Note carefully, I did not specifically refer to your program as one which was canidate for trashing. If you felt this way you were mistaken.

What I did was issue a trashing warning concerning a specific application of random selection over the total set of elements.

It was nice of you to defend your program by saying it picks only 4 elements. Good for you. My trashing warning stands for those who attempt to do what the warning describes.

Thanks for being clear.

(edited) I read the code and there was no indication from the code in this thread that the the code is simply attempting to randomly pick 4 different tiles out of 9 as targets.

I believe you yourself should read the code you posted.

sophie · 07-11-2003, 05:50 AM

DNAunion : thisElementsMemoryLocation = memoryAddressOfBaseOfArray + [((thisElementsRowIndex * COLUMNS) + thisElementsColIndex) * sizeof(oneElement)]

Although this may seem true, in reality the mapping of virtual addresses to real addresses is achieved through what is called a memory map. The memory mapping registers of say the 80(x)86 family of processors has the capability to assign non-contiguous blocks of physical memory to contiguous blocks of virtual memory.

In the simple format contiguity has two levels, virtual and physical, but to the ordinary programmer these levels of abstraction are never evident.

I apologise for confusing you.

sophie · 07-11-2003, 06:04 AM

DNAunion, I am not sure what you are claiming here,

DNAunion: But the two subscripts are misleading�there is no real element [5, 1] in the array. That is, to access element [5, 1] the computer does not go down 6 rows and then over to the right 1 [sic, should be 2].

Firstly your terminology is incorrect. It is the compiler not the computer that resolves the array references. There is no going down, and over to the right, whatever you are trying to imply.

Finally subscripts are not misleading. These are a part of data structures and their use is mainly to model data access. Or as Nial would say, data flow.

NialScorva · 07-11-2003, 08:18 AM

I am merely expounding on the dangers of overwriting an array. You pointed out that my commenting on "off-by-one" isn't relevant because the bug in your code is due to a quick and dirty translation problem, not that it exists in your original. The "you" in my post was a hypothetical "you", not intended to refer to errors in your code. Next time I'll not be so informal and will use the third-person "one".

As to multi-dimensional arrays, how they are laid out in memory is *not* defined by the language spec, and thus can vary from compiler to compiler. You are right that &f[x][y] == f+x*SIZEY+y on most compilers, including Visual C and gcc. My point is that this isn't required to be true on all compilers or machines.

Quote:

DNAunion: No, all of the char pointers in the 10-element one-dimensional array x are stored contiguously. And, each of the 10-char arrays that is allocated dynamically with new also consists of 10 contiguous elements. The only �array things� that are not (or at least may not be) stored contiguously in memory are those 10 individual, completely separate 10- char arrays generated at different times, on the fly.

Except that the compiler is absolutely allowed to implement your multidimensional array using dynamic memory, exactly the way I did, behind the scenes and not tell you about it.

One possible reason is pointer alignment on some machines. A pointer might be able to only point to an address that's a multiple of 4, or more likely it's a lot faster to point to such a word boundary.

What happens when you have "char x[3][3]" on a machine that can't point to an odd number? The compiler is allowed to slip a byte in between each array to make them line up if it likes, or as an optimization technique. Since you could deref constant aliases to x[0..2] at compile time and always be on a word boundary for faster loading from memory.

Quote:

DNAunion: Anyone with an ANSI Standard-compliant C++ compiler can run this code and see that the elements of the first dimension � which stores pointers � are stored contiguously in memory.

Which is irrelavent. My whole point is that to be ANSI standard, the compiler can treat multidimensional arrays in quite a few different ways that violate your &f[x][y] == f+x*SIZEY+y assumption. Just because most hold this to be true doesn't mean all will. You can say that compiler X on architecture Y does this, but not all ANSI compilers.

Mageth · 07-11-2003, 08:36 AM

DNAunion, by "blind luck", I mean the fact that your translation mistake didn't cause problems is more a matter of luck than of the nature of the ways arrays are or are not allocated. Such a mistake may not cause problems 5 times out of 10, 7 times out of 10, 9 times out of 10, or even 99 times out of 100, but there are cases where overstepping an array will cause problems, sometimes severe and immediate and thus relatively easy to detect and debug and sometimes subtle. The subtle ones are the worst - sometimes occurring in other functions/data structures and thus sometimes difficult to detect and almost always difficult to debug. Trust me, I've seen plenty of cases of that.

DNAunion · 07-11-2003, 05:06 PM

DNAunion: Okay, I�ve had time to rewrite the last part of my response to NialScorva:

Quote:

NialScorva: A multidimensional array is actually an array of arrays.

char foo[10][10];

is an array of 10 blocks of 10 contiguous bites. *Usually* these are stored contiguously, so that foo[0][9] and foo[1][0] are adjacent, but there is no such requirement in the language spec. It's perfectly valid for foo to point to an array of pointers to arrays. In fact, you can see this in the similar notation:

*****************************
char* x[10];
for(int i=0;i<10;i++)
x[i]=new char[10];
**********************************

You can then access x[0][1] and it should work and look just like a multidimensional array, though only the blocks of 10 in the final subscript are likely to be contigent.

DNAunion: Did everyone catch the switch? NialScorva started off with a two-dimensional character array of the sort I used, but then switched to a different array declared and populated differently. Any guesses why? Because the two are not compatible. The following code is invalid:

Code:

char foo[10][10];
for(int i=0; i<10; i++)
	foo[i]=new char[10];

DNAunion: Thus the switch. The following �two in one� program shows:

(1) that NialScorva�s first declaration, char foo[10][10], does create a linear arrangement of 100 contiguous char elements in memory.

(2) that NialScrorva�s second version, char* x[10];, creates an array of pointers, all of which are stored linearly and contiguously in memory.

Code:

#include <iostream>

using std::cout;
using std::endl;
using std::cerr;
using std::cin;
using std::hex;

int main() 
{

	char foo[10][10];
	
	// NialScorva's follow up code won't compile
	// using his above declaration.  That's why 
	// he switched arrays on us.
	//
	// for(int i=0; i<10; i++)
	// {
	// 	 foo[i]=new char[10];
	// }


	int row, col;
	for (row = 0; row < 10; row++)
	{
		for (col = 0; col < 10; col++)
		{
			cout << hex << (int)&foo[row][col] << endl;
		}
	}
	char junk[80];
	cout << endl;
	cout << "The individual elements of the two-dimensional ";
	cout <<	"character array are stored linearly, and ";
	cout << "contiguously in memory." << endl << endl;
	cout << "Press [Enter] key to continue...";
	cin.getline(junk, 80, '\n');
	cout << endl << endl;

	// --------------------------------------------


	char* x[10];
	for(int i=0; i<10; i++)
	{
		x[i]=new char[10];
	}


	int index;
	for(index = 0; index < 10; index++) 
	{
		cout << &x[index] << endl;
	}
	for(index = 0; index < 10; ++index)
		delete x[index];
	cout << endl;
	cout << "All array elements -- here, pointers to " ;
	cout << "'strings' -- are stored contiguously." << endl;
	return 0;
}

Lobstrosity · 07-11-2003, 05:18 PM

Quote:

Originally posted by DNAunion
DNAunion: Thus the switch. The following �two in one� program shows:

(1) that NialScorva�s first declaration, char foo[10][10], does create a linear arrangement of 100 contiguous char elements in memory.

(2) that NialScrorva�s second version, char* x[10];, creates an array of pointers, all of which are stored linearly and contiguously in memory.

How is it that you manage to continually avoid addressing the actual points people keep making. There was no switch. If I understood correctly, NialScorva was using the code as an analogy. The point that's being made is that the decision on how arrays will be stored in memory is dependent on the specific compiler you are using and the system your program will be running on. There is no guarantee that every compiler/system will store the blocks contiguously. This is all you need to respond to:

Quote:

NialScorva:
A multidimensional array is actually an array of arrays.

char foo[10][10];

is an array of 10 blocks of 10 contiguous bites. *Usually* these are stored contiguously, so that foo[0][9] and foo[1][0] are adjacent, but there is no such requirement in the language spec.

If your program makes an assumption that is not enforced by the language specification, your code could burn you should you change systems or compilers (or should newer systems/compilers decide to implement memory-storage differently). It's as simple as that. In short, such code is more of a hack than an exemplar of good programming style.

DNAunion · 07-11-2003, 05:31 PM

Quote:

Sophie: again DNAunion,

I selected one line of code to issue a trashing warning. Note carefully, I did not specifically refer to your program as one which was canidate for trashing. If you felt this way you were mistaken.

DNAunion: No, then you misspoke terribly. Let�s all take a look again.

Quote:

Sophie: I must issue a trashing warning :

nFoundOne = 0;
while (nFoundOne == 0)
{
nIndex = (int) GetRandomNumber(0, nLetteredTiles - 1);
...
}

The set of solutions which use randomization to access every element in a set once, is prone to what is termed trashing. This means if one randomly picks numbers from 1..n, it is not true that n tries will eventually visit every every element.

Mostly you end up with 2n or 3n computations to visit every element. The elegant solution to this is randomly choosing 85% to 90% of the indicies, then sequentially selecting every non-selected item. The complexity of this algorithm is fixed at 1.8n, and as such the overhead is fixed and known.

A true randomiser may never pick one entry and this may entail your program may run into the infinity clause, even though you think it may not.

DNAunion: You issued your trashing warning, ending it with a colon, indicating that the thought was not complete, and then immediately followed by posting several lines of my code. Gee, how in the world could anyone conclude that you were talking about my code?!?! That conclusion is practically forced upon one.

But let�s continue. In your response, you included only my code. You then use the pronouns you and your a total of three times, another clear indication that you are referring to my code, especially when you say, ��this may entail your program�� Now who's is the only program you quoted from in your post? Mine.

So don�t go trying to blame me for misconstruing you when what really happened (if we believe you now) is that you completely screwed up.

DNAunion · 07-11-2003, 05:51 PM

Quote:

Sohpie: DNAunion, you missed the last point, which was clarified as virtual contiguity. Underline virtual contiguity.

It appears contiguous but in actual memory it may not necessarily be contiguous. However for your simple purposes of using arrays, you can well imagine it is contiguous.

DNAunion: Thanks for conceding the point to me, though, it�s not really like you had a choice.

By the way, you do realize that your "contiguous memory" is completely irrelevant to the discussion of my code, don't you? Several people pointed that out to you.

No, you aren't talking over my head, you're just not talking about what matters.

07-11-2003, 05:29 AM	#61
sophie Veteran Member Join Date: May 2003 Location: On the road to extinction. . . Posts: 1,485	DNAunion DNAunion, you missed the last point, which was clarified as virtual contiguity. Underline virtual contiguity. It appears contiguous but in actual memory it may not necessarily be contiguous. However for your simple purposes of using arrays, you can well imagine it is contiguous. Sorry I was talking above your head. For your purposes you are correct.

07-11-2003, 05:36 AM	#62
sophie Veteran Member Join Date: May 2003 Location: On the road to extinction. . . Posts: 1,485	DNAunion again DNAunion, I selected one line of code to issue a trashing warning. Note carefully, I did not specifically refer to your program as one which was canidate for trashing. If you felt this way you were mistaken. What I did was issue a trashing warning concerning a specific application of random selection over the total set of elements. It was nice of you to defend your program by saying it picks only 4 elements. Good for you. My trashing warning stands for those who attempt to do what the warning describes. Thanks for being clear. (edited) I read the code and there was no indication from the code in this thread that the the code is simply attempting to randomly pick 4 different tiles out of 9 as targets. I believe you yourself should read the code you posted.

07-11-2003, 05:50 AM	#63
sophie Veteran Member Join Date: May 2003 Location: On the road to extinction. . . Posts: 1,485	possible DNAunion : thisElementsMemoryLocation = memoryAddressOfBaseOfArray + [((thisElementsRowIndex * COLUMNS) + thisElementsColIndex) * sizeof(oneElement)] Although this may seem true, in reality the mapping of virtual addresses to real addresses is achieved through what is called a memory map. The memory mapping registers of say the 80(x)86 family of processors has the capability to assign non-contiguous blocks of physical memory to contiguous blocks of virtual memory. In the simple format contiguity has two levels, virtual and physical, but to the ordinary programmer these levels of abstraction are never evident. I apologise for confusing you.

Thread Tools	Search this Thread
Show Printable Version	Search this Thread: Advanced Search

07-11-2003, 06:04 AM	#64
sophie Veteran Member Join Date: May 2003 Location: On the road to extinction. . . Posts: 1,485	DNAunion, I am not sure what you are claiming here, DNAunion: But the two subscripts are misleading�there is no real element [5, 1] in the array. That is, to access element [5, 1] the computer does not go down 6 rows and then over to the right 1 [sic, should be 2]. Firstly your terminology is incorrect. It is the compiler not the computer that resolves the array references. There is no going down, and over to the right, whatever you are trying to imply. Finally subscripts are not misleading. These are a part of data structures and their use is mainly to model data access. Or as Nial would say, data flow.

07-11-2003, 08:36 AM	#66
Mageth Contributor Join Date: Jul 2001 Location: Deep in the heart of mother-lovin' Texas Posts: 29,689	DNAunion, by "blind luck", I mean the fact that your translation mistake didn't cause problems is more a matter of luck than of the nature of the ways arrays are or are not allocated. Such a mistake may not cause problems 5 times out of 10, 7 times out of 10, 9 times out of 10, or even 99 times out of 100, but there are cases where overstepping an array will cause problems, sometimes severe and immediate and thus relatively easy to detect and debug and sometimes subtle. The subtle ones are the worst - sometimes occurring in other functions/data structures and thus sometimes difficult to detect and almost always difficult to debug. Trust me, I've seen plenty of cases of that.

Freethought & Rationalism Archive

The archives are read only.