Thank you for the detailed discussion. I don't have a lot to add at this point.

I will say that your comment on virtualized DMA engines is very interesting to me, however.

At a quick look, the XOR trick depends on there being an integral type large enough to hold the pointer type, and if there is it appears to be legal. A strictly conforming implementation apparently might not have a sufficiently large integral type, although I can't imagine anybody writing one.

The XOR trick is inherently implementation dependent, since it requires manipulating a pointer while it's an integer. I think it's fair to assume anyone using it is only using it on a machine with a sufficiently wide integral type.

What's not strictly conforming in my mind is performing any manipulation on the pointer while it's represented as an integer. However, you would be correct to point out that if reinterpret_cast< sufficient_int_type >( pointer ) gives me value X, and regardless of the shenanigans I pull with X, as long as I supply that exact same bit pattern X to reinterpret_cast< orig_ptr_type >( X ) I should get the original pointer back. And if round-tripping a pointer through an int back to a pointer is strictly conforming, then the XOR trick is strictly conforming too.

(At the risk of sounding like I'm shifting goal posts, I do know the C++11 standard tried to get some wording in there to support garbage collectors. I have no idea how that language reads against the XOR trick. I do know the XOR trick would confuse GC by hiding pointers from it though. As for whether GC could ever work out-of-the-box in real, non-trivial C++98 programs that have been around awhile, allow me to show you my deeply skeptical face. You pretty much need a C++11/14 program written in a more modern style.)

In any case, can we both agree that the XOR-pointers trick is a trick best left in the last millennium in most modern systems?

The extra pointer could be legally put into the padding by a sufficiently smart compiler, I believe.

I don't believe structure copies are guaranteed to copy padding.

It's also moot on most systems: If pointers have the strictest alignment of any type on a given platform, there will never be contiguous padding large enough to accommodate a pointer. The only cases I can think of where pointers don't share the strictest alignment are systems with 32 bit pointers, but require 64-bit alignment for double and/or long long. Surprisingly (or maybe not), 32-bit x86 only requires 4 byte alignment for double and long long.

So even if it was legal for the compiler to play games on you within the padding in a POD type, on most commercially viable systems you'll never have the padding you need in a contiguous field.

We're rather far into the "theoretically possible, but with such restrictions that nobody would bother."

I wasn't saying the XOR trick is illegal in C++. (It does, however, rely on implementation defined behavior, so you likely couldn't use it in a strictly-conforming program.)

I was saying that it's illegal for the compiler to undo bad data structures, such as replacing your XORed pointers with proper prev/next pointers. If you have something like this:

struct ugly {
uint64_t prevnext;
};

Where 'prevnext' is the XORed pointer, the compiler isn't allowed to replace it with something more sane like:

struct ugly {
ugly *prev, *next;
};

...or even...

struct ugly {
uint32_t prevnext;
};

...if it figures out you picked an oversized integer for the storage.

TheRaven64 pointed out some cases where it can be legal for the compiler to rearrange / modify bad structures, but the gains tend to be minimal.

As I recall, the C++ standard does put some requirements on structure layout, as least for standard layout PODs:

* Minimum size of 1 for a structure so that each element of an array of empty structures has a distinct address

* Distinct addresses for all non-bitfield members

* Pointer to struct is convertable to pointer to first member and back

* Increasing addresses for members in order of specification

* Optional padding as required between members and at the end of the structure.

* Layout compatibility between identically declared standard-layout structs for their common initial sequence. (That's a mouthful!)

(There may be some others I'm forgetting... That list was off the top of my head.)

If a compiler wanted to rearrange a structure (say, to eliminate or minimize padding, or to eliminate unused members), it'd have to prove that the program didn't rely on any of the guarantees the standard offers that the compiler's otherwise violating. Violations of the standard by the optimizer are legal as long as you don't get caught. ;-)

Actually, it isn't if the compiler can prove that the layout is not visible outside of the compilation unit.

Ok, that's fair. You also need to ensure its memory image isn't visible to, say, a char*. (That pesky char* exemption in the standard that allows you to write memcpy and memmove is no friend to alias analysis.)

For example, if the address of one of these structs is never taken, then the struct never need live in memory even, so its layout is irrelevant. If addresses do get taken but you can find all the uses of those addresses, then yes, you could play games with the layout if it was impossible for the program to notice. That's perhaps a stronger criteria than compilation unit boundary, though.

What's the justification for compilation unit boundary? It seems like you could expose the layout of the struct (and therefore any compiler shenanigans) through other means within a compilation unit. offsetof comes to mind. :-)

My initial gut reaction is that nearly any interesting data structure wouldn't qualify for this optimization. :-) Sounds like your data matches.

It's much more interesting in environments with on-the-fly compilation, because then you can adapt data structures to use.

Cool. That reminds me of an experiment I heard about at HP. They implemented a PA-RISC to PA-RISC dynamic translator that used run-time information to reoptimize the code. The overall speedup (including the cost of the translator) was in the 5% - 10% range. Here's the paper.

Even then, you can do it outside of the compiler (for example, the NeXT implementations of the Objective-C collection classes would switch between a few different internal representations based on the data that you put in them).

I suppose you could do that in C++ with template specialization. In fact, doesn't that happen today in C++11 and later, with movable types vs. copyable types in certain containers? Otherwise you couldn't have vector< unique_ptr< > >. Granted, that specialization is based on a very specific trait, and without it the particular combination wouldn't even work.

In theory, you could also specialize based on, say, sizeof( item ). I suppose that then becomes an ABI issue with the C++ standard library. Bleh.

I have a love-hate relationship with C++. :-)

That's cool, and I could see how you might get something out of it if it actually digs in on some of the tougher topics. Pipelining doesn't really affect your code until you start doing things that expose the pipe's depth, such as branches, load instructions, multiply/divide and floating point. It can be a good lesson on why instruction scheduling matters, whether it's handled by software or hardware.

In my comment above, I mentioned a class that I wasn't sure students were getting much out of, the bar of accomplishment seemed pretty low, and the things focused on seemed esoteric as compared to what actually matters. For example, the professor had the class design a machine to implement quicksort on bytes, with a memory that was only word addressable. That just seems like a pointless brain teaser.

I think it'd be far more relevant to model a simple RISC pipeline and look at the impact of, say, a branch predictor in the context of some common algorithms. Or maybe the impact of memory latency on various data structures. "Hey kids, this is why linked lists suck." "Let's see the horror show behind switch-case statements and VTables!" :-)

In other words, I was picking on that particular professor and course, not the idea of such a class.

I have worked with compilers that auto-vectorize, unroll and jam loops, collapse/coalesce loop nests, interchange loops, software pipeline instructions, and so forth. (The compiler we ship for our DSPs at work does all of these things.) And there are some compilers that will tile loop nests into chunks that fit in L1 and L2 caches, although I don't know that I've used one, unless GCC's picked up some new tricks.

But yeah, rewriting data structures, such as undoing XORed-pointer lists? I agree with you: BS! Heck, in C / C++, such as transformation is actually illegal.

I wonder if this is a case of confusing the compiler with the standard library? Most people I know who aren't compiler geeks don't really distinguish between the compiler and the standard libraries. "I don't know; it comes with the compiler!"

For example, I know if I use std::map in C++, that I'll get certain big-O guarantees. But, I don't know how it's implemented underneath. Is it an RB tree? An AVL tree? A B* tree? Some other structure? I don't actually care, but I do expect whoever's writing the standard library to pick an appropriate representation for current hardware. And I know if I upgrade my compiler (which upgrades the standard library), I may get an improved implementation of the standard algorithms.

I've met CS grad students (grad students!) that have never programmed assembly language, or really anything lower than Java. I've worked with other freshly minted CS majors that have barely gotten a taste of machine organization, computer architecture, or any of these lower level concepts. Or, they were exposed to it, they did the bare minimum to survive the architecture class with no intention of retaining the material. And, I've worked with others that were stellar and knew their stuff inside-out.

Sure, the better schools do a better job of covering computer architecture basics. But it seems a fair number cover this material rather perfunctorily.

In any case, this is a bit off the topic. I expect CS folks to know their job and their curriculum, and complaining about schools with shoddy CS curricula vs. schools that do CS right is missing the point.

Bill Nye's complaint is that most software writes (and he included that in a rather generic list of occupations, as opposed to singling them out specifically) aren't terribly scientifically literate. That has almost nothing to do with Computer Science, and more to do with how many folks fall for pseudoscientific claims and hokum.

Silicon Valley has a unusually high concentration of anti-vaxxers. Explain that. No amount of compiler theory, digital logic, virtual memory, pipelining, algorithm analysis, or big-O notation can fix the scientific literacy gap that anti-vaxxers fall into. And it's that sort of scientific literacy Bill Nye was going on about.

I have it here on my desk. IEEE 754-2008 defines a binary representation for decimal floating point, so that people can move away from BCD (Binary Coded Decimal). Your observation doesn't invalidate Lumpy's point that the computations and electrical representation are all in binary.

I'd argue that that's not so computer science as it is computer engineering. Computer Architecture courses tend to be more the domain of EE departments than CS departments, in my experience. I'll grant you that enlightened schools do a better job of combining them. The school I went to, which has an excellent EE department, didn't combine them. (Our CS department at the time was made up primarily of math professors that couldn't hack teaching math.)

I find it hard to imagine a pure CS undergrad program going to the extreme of designing and building a pipelined processor. I have seen some CS architecture classes that try to have students architect and simulate simple machines. The bar was pretty low, and it wasn't clear to me what the students were getting out of that particular class.

Granted, I'm saying all of this from the jaded perspective of someone who's been in the chip industry 18 years, and has had the pleasure of working with a wide range of skill sets. I've also seen how much there is to learn after college. I do think EEs could stand to learn more CS, and CS folks could stand to learn more EE, but I don't know what you'd displace in the existing curriculum to fit it all in. Some of this you just have to learn on the job if you don't want to be stuck in college for 6 to 8 years.

Countries can't do it, because it costs too damn much. It isn't just focusing on the problem at hand, but making it much cheaper to put things into space... a task that governments are ill suited to perform as well for multiple reasons. The economic justification for going to Mars simply isn't there.

I also have doubts that even the supposed $10 billion figure that Mars One claims to be able to raise is going to be sufficient to pay for everything needed on Mars for even a small crew of say a dozen people.

Surprisingly, pretty good. I've seen figures of less than one bullet in a thousand fired in combat even hits a person, even with highly trained soldiers on both sides that are even trying to aim... like was the case at the Battle of the Bulge during World War II or fighting in the trenches of World War I with aggressive attacks. For soldiers in some of the more recent wars that the USA has been in, you have a much better than 90% chance of surviving combat engagements, and for some units definitely higher than 99% of the soldiers will return home without any combat injuries of any kind beyond PTSD. If you can get a medic to get ahold of you and pull you from the front line, your odds of survival even with combat injuries are pretty damn good.

This is a pretty lousy example to give.

I would agree with your basic sentiment, but my problem with Mars One and the guys trying to do this is that they are biting off far more than they can chew by going to Mars in the first place. If the goal is to get people into space, they should start out by simply getting private individuals into space (including some of these "candidates"). It is proven technology, where flight slots are definitely available for a proven price (currently about $50 million per seat) and a whole lot of eye candy and places to film in even exotic locations like Star City, Russia to show what it is like to go into space.

Yeah, lets do this thing, but do it on a reasonable level first before you decide to bite big and try to do something that all of the largest spacefaring countries of the world combined simply can't do right now. It can be done on a bite sized basis where these producers could earn some credibility before going to Mars.

Mars One most definitely haven't done that.

These guys definitely deserve to be heckled right now as there are basic questions even related to the physics of how they plan on accomplishing this thing they propose, much less trying to work out how they plan on getting it financed with fanciful scam artist style projections of future income that is most definitely not proven.

There is such a stable society. It is called a hunter-gatherer society where people congregated into groups of roughly 100-500 or so people (usually splitting into two or more groups when it got to that larger size even if they still maintained relationships with those other groups). The problem here is that cities were built that broke that kind of society where the hunter-gatherers have been pushed to the fringes of the world and quickly disappearing as they get pushed into increasingly marginal land.

What hasn't been mastered is the concept of a city, especially when the number of people gets over a million or so people in that city. That is also a very new concept, where it wasn't until the late 18th Century that London & Paris reached this milestone of size and became the major industrial cities that we know today.

There are a couple earlier historical examples like Rome and perhaps Yaodharapura (home of the Angkor Wat). Neither city was sustainable at that size. Mostly, our experience in dealing with industrial societies is mostly stuff found in the last century or so and by even historical standards so recent as to not have much of a precedent to even compare against.

I have tons of programming books, engineering books, algorithms books, data manuals, etc., all of which I read for enjoyment and to better myself as an engineer. I have read some fiction, but it's been a long while since I spent much time reading fiction. And then there's puzzle books which don't really fall into either category.

When I want fictional entertainment, I'll turn on the TV or go watch a movie.

Was that the one that Rihanna was stationed on?