On which architectures are invalid invalid pointers computed?

Question

int* a = new int[5] - 1; 

This line alone causes undefined behavior according to the C ++ standard, because a is an invalid pointer, not one end. At the same time, this is the zero utility way to create an array based on 1 (the first element is [1]), which I need for the project.

I am wondering if I need to avoid this or if the C ++ standard is simply conservative to support some bizarre architectures that my code will never run anyway. So the question is, which architectures will be the problem? Are any of them known?

Edit: to see that the line above actually causes undefined behavior, take a look at this question .

Edit: Dennis Zickefoose indicates that compilers can do something when undefined behavior is called, so both the compiler and the processor must offer guarantees outside the C ++ standard for this code to work. I ask a question about whether any modern C ++ compilers have it.

Answer 1

The hardware for conducting checks is present in all x86-processors, we just do not use it at the moment in the most popular operating systems.

If you use the segmented memory architecture that we used for 16-bit systems, allocation is unlikely to return segment:0 . In this case, you simply cannot subtract anything from this address!

Here is the starting point to read about segmented memory and why loading an invalid segment is not possible:

http://en.wikipedia.org/wiki/Segment_descriptor

You have to decide if this will happen for your code, or perhaps you can define an overloaded operator[] that handles the offset for you.

Answer 2

In any case, a well-defined, zero waybill way to create a single array is as follows:

 int* a = new int[6]; 

There the problem is solved. ;-) (But an interesting question yet.)

Answer 3

Note. I am not going to answer your question. But judging by the comments, some experienced SO members don't seem to know that this behavior is actually undefined ... So, somewhere around here we have to cite a chapter and a verse in some standards.

So...

From C ++ 0x standard (draft) , section 5.7 (5), discussing the behavior of adding a pointer (my highlight):

When an expression having an integral of type is added or subtracted from the pointer, the result has the form of a pointer operand. If the operand pointer points to an array element, the array is massive enough, the result indicates the offset of the element from the original element, so that the difference between the resulting indices and the original array elements are equal to the integral expression. In other words, if the expression P points to the ith element of the array object, the expressions (P) + N (equivalently, N + (P)) and (P) -N (where N has the value n) indicate, respectively, I + nth and ith elements of the array, if they exist. Moreover, if the expression P points to the last element of the array object, the expression (P) +1 indicates one after the last element of the array of the object, and if the expression Q points one after the last element of the array object, the expression (Q) -1 indicates the last element of the object array. If both the pointer operand and the result point to elements of the same array object or one last element of the array object, the evaluation should not overflow; otherwise, the behavior is undefined.

A similar language appears in each version of the C and C ++ standards. Pointer arithmetic that produces a result outside the bounds of the array (plus one) has undefined behavior, even if you never play the pointer, and it always has been.

...

Now, here is my own answer to your question: you are asking the wrong question. Even if it never poses a problem for any current computer and compiler, you should be worried about future machines and compilers, because 90% of the cost of all software is maintenance. If you strictly code the specification, you guarantee that your code will work in any system that conforms to the standard, whether today or after 50 years. The risk of introducing subtle errors for those trying to keep your code in the future is almost never outweighed by any benefits today.

In addition, I am skeptical about the difference in performance in the real world. (I’m not saying that you’re wrong, I’m just saying that I’m skeptical.) Although I admire your attempt to create the “fastest binary heap in the world,” I suspect that you underestimate the influence of the memory hierarchy. Of course, I think that "multiply by two" is twice as fast as "multiply by two and add one." But I also think that fetching a cache line from main memory is hundreds of times slower than either.

If you are comparing your heap by doing a small set of operations on it over and over again without doing anything else, you are probably fully working with the L1 cache. But this is completely unrealistic. In real life, a bunch is just a small part of a large algorithm; the likelihood that all this will always sit in the L1 cache is very low, unless this algorithm is trivial. Thus, the cost of access to memory is likely to dominate any real scenario.

Answer 4

I think this can be dangerous for some old 16-bit x86 systems. The address is "split" between the address register and the segment register, and I would suggest that this could result in an invalid value being loaded into the segment register, which will throw an exception.

This is probably not a problem, because these days it is not a common architecture.

Answer 5

You asked a few questions here. One of them was "this is what I need to avoid." My answer to that is yes. You are creating a pointer indicating that you do not have your own memory. You should avoid this. Using [0], a completely legal statement leads to undefined behavior. What does your corresponding delete [] look like?

Another question depends on what you consider fancy. Is hardware with dedicated registers for pointers validated as fancy? The real question, does it seem like you need portable code? If so, avoid this. If not, you can still avoid this. Using this depends on your attitude to serving the code, because it hits me like something that can easily call the person who inherits your code.

Answer 6

People have already mentioned (a) the lawyer's strict language interpreting the standard, and (b) the x86 segments, usually in 16-bit code (but also on some older 32-bit OSs).

Let me mention another example close to my heart:

Andy Gleu. 1990. An empirical study of indexing OR. SIGMETRICS Run. Eval. Rev. 17, 2 (January 1990), 41-49. DOI = 10.1145 / 378893.378896 http://doi.acm.org/10.1145/378893.378896

What am I.

In this article, I proposed a set of instructions that used the OR mode rather than ADD as the memory addressing mode.

Now, since C programmers can always do

 int* a = new int[5] + 1; 

compilers should handle these things correctly.

But at the same time, they may be less effective.

It turns out I'm not the only one who thought about this. Some real transport computers have used this technique, although I have no links.

Anyway, this is just an example.

---

In general, although

a) what you offer will work on most machines (of course, most machines are x86s running Windows or Linux or ARM, working with UNIX derivatives such as iOS and Android).

b), but it may be illegal. This may break some compiler optimizations, be interrupted by some compiler optimizations, etc.

By the way, on x86 1-based arrays cost a bit more code and almost nothing in machine code. If you say something like

 template<typename T,uint size> class One_Based_Array { private: T array[size]; public: T& operator[](uint i) { return array[i-1]; } }; 

used as

 One_Based_Array<int,100> a; int tmp = a[i]; 

machine code will look something like this:

 MOV EAX, a.array-4(ebx) 

i.e. 1-based things can usually be stacked in x86 basereg + indexreg + offset mode. On some machine it costs nothing, as a rule, although the code may be a bit more.

In fact, Intel compilers often generate code that looks like

 ebx = -i MOV EAX, address_of_end_of_array[ebx] 

i.e. using indexing with subtraction, and not with the addition, or with the addition of a negative number, since testing against 0 is more effective than testing against + N.