Re: 6502 illegal opcodes questions

["mdj" <mdj.mdj@gmail.com>]

Michael J. Mahon wrote:

I was going to refrain from posting again to this discussion, but we've
covered so many different areas, some of them orthogonal. I feel like
this thread categorises me as one of those "constrained language"
types. I assure you this is not the case. Indeed, my current favorite
language is Ruby, a typeless, dynamic language that imposes almost NO
restrictions over the programmer whatsoever. There are of course,
benefits and tradeoffs in every language feature, and unlike those who
believe that the book on imperative language design has already been
written, I believe all we have so far is a preface. A bunch of ideas
expressed in a bunch of languages, some of them very similar, some of
them very different.

I will maintain that most if not all of the contentions discussed in
this thread are the result of stigma, and that time has solved the
issues around many of them, with more on the way.

> >>But much of the discussion here has been driven by "strongly typed"
> >>and "restricted" languages and semantics vs. "weakly typed" and
> >>unrestricted (nonportable) languages.
> >
> >
> > And much of the argument against being that strongly typed yields
> > inefficiency, a point I strongly disagree with.
>
> And I support your disagreement.  My issues are different,
> and relate to the fundamental inability of any language to
> save programmers from undisciplined tendencies.

I agree that people can't be 'saved', but I maintain that small
improvements over time can yield real benefits. If an old idiom proves
to be faulty, give people an alternative, make it easier to use than
the idiom, and let evolution take its course...

> >>The presumed superiority of the former is that it either:
> >>1) makes it harder to do bad things accidentally,
> >>2) makes it harder to do bad things intentionally,
> >>3) makes it easier to do good things accidentally, or
> >>4) makes it easier to do good things intentionally.
> >>
> >>I note that 1) and 3) (the unintentional flavors) can be readily
> >>supported, and can be construed as support for relative newbies.
> >
> >
> > Not just newbies, though. Plenty of good programmers have used
> > techniques that over time have proven to be problematic. Some of them
> > realise the problems and stop using the techniques, some of them don't.
> > It's common to end up in a heated discussion with a  fine engineer who
> > doesn't want to change an obviously flawed approach because they cannot
> > see the future benefits of doing so.
>
> And, ironically, sometimes they turn out to be right.

I agree with you here. I've been trying to focus on example where time
has proven them wrong.

My best example of why these are 'wrong' is the net result of some of
these decisions. The last few years have shown up many, many security
vulnerabilities in operating systems, many of which exist because of
adherence to I/O idioms that rely on supposedly 'efficient' language
constructs.

The cost to industry, both IT and not, of these vulnerabilities is
immeasurable. The cost to the reputation of some IT companies has also
been immeasurable. While most of these tend to be in 'legacy' code,
ironically the sources of the largest quantity of these issues have
been places where the code *should* have been more modernised.

Removing explicit pointer assignment from non-operating system code has
a massive effect on reducing these problems.

My experience has shown that there is no machine inefficiency of any
measurable amount introduced by this change. There is a degree of human
inefficiency though. I myself lamented the features I lost when moving
from C/C++ to Java. I cursed the inefficiency of not being able to do
things a certain way. Over time though, I learned that not only was
there other ways to express such constructs that was just as efficient,
but that those ways actually had another benefit: The code was more
readable, and safer. The time 'lost' to my having to learn a few new
techniques was well worth it.

In short, my motivation for removing such features, is one of
pragmatism, not ideology. When engaging in projects for personal use, I
prefer 'unconstrained' tools as well.

> They are more devoted to their "principles" than to getting the job
> done.  And they seem oblivious to the fact that their principles are
> really just the "tradeoff du jour".

There is a very real issue in the programming profession, that
deadlines imposed by forces outside the control of development teams
will necessitate the 're-use' of code that has no business being
reused. We the users end up paying for this, and it's often the case
that even the best developers are forced to apply these techniques.
Fortunately though, it's a 'freeish' market, and organisations that
fail to learn from these follies will eventually fall prey to those
that do.

> Look at the history of language design--filled with religious fervor
> and yet as changeable as fashion.  The longest lasting phases have
> been the most pragmatic, and the shortest the most theoretical.
>
> I no longer await the language that will save us all.  In my
> experience, our salvation is up to us and our wits.  We may, from
> time to time, find a tool or method that we find useful, but there
> is no ultimate tool or method.  To imagine that there is is itself
> a great danger, since it makes us more dependent on tools and less
> masters of our own designs.
>
> I expect that you will say that wonderful language "X" actually
> improves our mastery of our designs, but I say that it does so only
> by constraining our thought in ways that are superficially beneficial
> but which are ultimately limiting--as only time will tell.

Yeah, see I feel that it's actually the opposite. Most of the benefits
of retaining a feature that has proven through time to be more
dangerous that useful is superficial, and that superficiality is in
fact the time needed for humans to retrain their minds.

There's an (old) saying, old habits die hard. In many cases, it
requires some external force or motivation to change an old habit, and
in the development world that often has to be removing the means by
which the old habit can propogate.

In almost every case where I've spoken in depth with people upset about
losing an old feature, it's not due to an inability to express
themselves with new ideas, but the fact that some old code they'd
reused a hundred times won't work anymore. Frankly, I find this
attitude one of laziness. It is extremely costly considering that most
of the time the effort involved in either fixing or mitigating the
issue is very small, and usually requires nothing more than a bit of
education.

> A great designer can do great things in any language, but it will
> be much harder to do all the great things he can do in just one
> language.  Imagination will not be contained.

It doesn't need to be. I agree with you completely on this point. I
challenge anyone to come up with a piece of code that relies on this
freedom that cannot be expressed another way.

> You argue that a more formal notation prevents accidental errors,
> and so improves the result.  But I argue that it also obstructs
> brilliant design strategies containing elements considered harmful
> by the language designer.

I some cases this may be true, but it's difficult to come up with an
example isn't it? It's fairly easy to show that you lose nothing by not
being able to point at a specific location in memory. Of course if
you're controlling hardware this is not the case, but I'm certainly not
going to argue that you should write device drivers in a language void
of pointer arithmetic :-) Although one might consider that even in this
case, it's possible to engineer out at the hardware level the need for
such facilities.

> Indeed--who can fathom all the reasons for someone
> wanting to "beat the system"?

That's exactly it. Unfortunately these days, it's people beating the
system from the outside, via some old techniques, exploiting old code.

One might argue that the solution is to fix such code as to alleviate
the issue. I'll say that this is overly optimistic given the nature of
our industry. Treat the cause, not the symptom. There will always be
another symptom while the cause it it still exists.

> >>It is certainly possible to write non-portable code in any sufficiently
> >>complex system, simply by exploiting some irregular behavior--and there
> >>will *always* be some irregular behavior to be exploited.  ;-)
> >
> >
> > The hardest part of the problem, and one yet unsolved by language
> > design.
>
> Not only unsolved, but unsolvable in any finite system.

While you're completely right, this doesn't provide justification for
not minimising the problem when it's easy to do so. Failure to mitigate
this as complexity grows will send you flying into a glass ceiling that
could have been considerably higher.

> I realize that there are more complex initialization issues than the
> simple "uninitialized data" one I have discussed, but it's a start.  ;-)

I've used similar techniques. An example is using small page for
virtual memory and allocating memory only once per page. While
wasteful, it generally causes many errant accesses to fire segmentation
violations that are easily fixable.

> Think about it.  Any Turing complete language can be used to write
> a simulator for any other Turing complete machine.  There is no way
> to prevent this without sacrificing the universality of the language.

Of course. I was referring more to cases like lexical analysis and
parsing, where the conventional approach is to use tools like flex,
yacc, and friends. While these tools are brilliant, they point to
deficiencies in languages that could be corrected. Access to features
like that at the language level would mitigate the need for both these
tools, and the need for the 'dangerous' language feature they tend to
depend on (I mean goto, not pointers)

> I only note that there are successful patterns which are *not* made
> of OO concepts, as well.  Perhaps some of the most useful ones...

Indeed many of the patterns are also applicable to non-OO designs. OO
at the end of the day is just another level of abstraction above
structures and functions, allowing convenient paring of related
structures and functions, resulting in more manageable code. Going back
to languages that lack it is very 'constraining' :-)

I found the hype around OO that flew about over the last 15 years to be
quite ridiculous. Had it been sold for what it actually is, rate of
adoption would be far higher.

On a related note it's amusing that people consider a language like
Java to be more constrained than C++, when the features missing are
actually C features for the most part. If we compare them as OO
languages, the language that ends up being the more constrained is not
the one you might expect, and this is a large part of why people are
using Java's, C#'s, etc. These languages derive their OOness from the
Smalltalk-80 school, rather than the Simula school.

> >>If it were not for languages with explicit pointers, all our current
> >>"object oriented" languages would never have come to be.  The first
> >>such programs were written in assembly language, and were far more
> >>versatile and efficient in their realm than comparable programs
> >>written today.  (Sutherland's Sketchpad comes immediately to mind.)
> >
> >
> > Sure. It's worth pointing out though that explicit pointers aren't
> > necessary to achieve efficient designs, just as, on 32 bit platforms
> > anyway, there's no need to write position dependant code. If you're
> > targetting a 6502 or even 68000, you have to make some compromises, but
> > those restrictions simply no longer exist, and the need for techniques
> > that allow for the restrictions are gone with them.
>
> But all efficient (?) implementations of objects rely heavily on
> pointers.  And "simulated" pointers are still pointers, just less
> efficient.

We used to argue that the overhead of function calls was too high in
many cases too :-)

The point to remember is that such inefficiencies are only costly
inside the critical code path. This critical code path is relatively
small, and a modern runtime based compiler can easily spot the critical
path(s) and optimise them out. A big advantage of this approach is that
during this process, you can spot scope of calls to critical methods,
and when the scope turns out to be small, you can eliminate the
dynamicism, often to the point of inlining and achieve a very fast
critical code path.

One of the biggest disadvantages of C++ is that you have to make these
decisions when you write code, and the compiler must 'guess' what is
going to be critical, usually by optimising absolutely everything it
can. This results in a very large, unreasonably large code footprint.

Unfortunately though, since the compiler must make optimisation
decisions at compile time, it has to obey the scoping rules that were
decided by the programmer, which usually turn out to be suboptimal.
Even if they were optimal for one particular use case of a modules,
they might be suboptimal for another.

Generally speaking, this results in VM based runtime compilers
significantly outperforming other techniques.

> Position-dependent code is irrelevant, since in a 64-bit virtual space,
> every procedure/module ever written can be assigned a unique location!
> Virtual memory makes relocation unnecessary (though perhaps occasionally
> useful).

It's also worth considering the performance advantages you can get from
eliminating explicit memory reference in such an environment. Such an
approach allows the possibility of coalescing memory boundary
restrictions to improve efficiency. You can load a lot of Java
programs into the same 64 bit address space. How many C/C++ programs
can you *safely* load into the same address space?

How many address boundaries that have to be crossed by marshalling and
copying data can be coalesced by this approach? How much inefficiency
exists today in software that enforces the older approach? How much of
it is only necessary because of the potential for an unsafe program to
crash a system?

Often, gains in efficiency come from increasing flexibility.

> > As we've discussed, it's possible to write portable code in languages
> > like C, provided you're *very* careful. Good designers can achieve
> > this, and not compromise efficiency either. The obvious point is
> > though, what can the good designer achieve if he doesn't have to expend
> > unnecessary energies being conscious of issues that can be solved by
> > language design?
>
> You have *way* too much faith in language designers!  ;-)
>
> They make serious errors every day--and on behalf of thousands of
> victims, er, users.
>
> Did you actually *read* Kahan's criticisms of Java numerics?  (I
> realize that Kahan is a brilliant and compulsive polemicist, but,
> dammit, he also has this nasty habit of being *right* sometimes.  ;-)

> His point is that what Java's designers didn't understand, they
> botched.  Actually quite understadable.  And he gives cogent
> examples of the consequences and simple recommendations to fix
> the problems--which were not acted upon!

Of course. I read it in 1998 when it was published again when it was
raised as a concern in this thread. I noted when I first read it that
all of the concerns raised could be addressed in an upwards compatible
way.

The big thing that Java designers got right was to leave out features
that would bind them later on. The intervening years have seen the
language improved, both in syntactic expression AND performance. The
portability of it's language definition has allowed it to evolve in
ways that it's predecessors have not, can not.

There are areas of course where C/C++ programs are still faster. There
are also many areas now where they are not. Over time, the number of
areas where there's a speed advantage for C/C++ is shrinking, and for
Java it's growing. You should also note that as the size and complexity
of programs goes up, the performance characteristics of the two
languages alters.

http://www.dmh2000.com/cjpr/index.shtml

Here's a more up to date comparison, showing both Python and Ruby as
well. Note that 7 years later, it's become appropriate to compare
scripting languages to Java C/C++ as well.

> When I first saw Java, and heard it proposed as a "universal"
> language, I noticed that it had vectors of vectors, rather than
> multidimensional arrays.  I knew immediately that this would be
> a huge performance issue for numerical programming, since I had
> the pleasure of working with Burroughs machines that had exactly
> the same limitation--and the same fundamental inefficiencies.

Java supports multidimensional arrays as well. Always has.
Interestingly, people tend when comparing Java to C/C++ to pick the
worst way to implement something in Java and the best way in C++.

This is essentially why I bother with these discussions. Obviously the
lack of primitive array types in Java would be a major impediment to
performance (At least until the VM's improve to the point of being able
to optimise Collection classes down to discrete implementations when
possible), but it simply isn't true.

> >>Further, though abstraction is essential, the best designers are
> >>characterized by a much wider "abstraction bandwidth" than is
> >>common, and their ability to span many levels of abstraction in
> >>their thought is what allows them to create *efficient* designs,
> >>rather than just "correct" designs.  (BTW, designers with "high
> >>bandwidth" are always in short supply, and much of todays software
> >>reflects their absence.)
> >
> >
> > I agree. I do believe though that such designers achieve more with
> > better languages and tools.
>
> Only to the degree that those tools do not limit their thought--and
> there is no tool that does not impose its limitations.

Agreed. We tend to disagree though, on what limits thought.

> "Thinking outside the box" sometimes means thinking outside the
> capabilities of your current tools.  Often the *real* brealthroughs
> come from just this kind of thought.

Indeed! Apparently though, it's perceived that when designers of newer
languages looked outside the box and chose to leave out a feature or
two that they had committed a grave error. One must evaluate both the
plusses and minuses of a change before condemning it.

It was easy in 1998 to point a figure at a technology like Java and go
"Slow! Inefficient!". Today, that's very much harder, and discussing
where each is more or less efficient than the other is frankly, beyond
most developers these days. Most rely on the judgements made by a small
group to form their "own" opinion, and I think it's very important,
particularly when things get to this level, that these judgements are
made from an informed perspective.

Note this is not an attack on you, I've very much enjoyed our
discussion, just a general observation of the industry we're in.

> >>I have been frequently appalled to find that *system* programmers
> >>working at the lowest levels of OS design are often almost completly
> >>ignorant of the *machine* implications of the code that they write.
> >
> >
> > And this is a problem that's only getting worse. You can only fit so
> > much teaching into a 3-4 year degree, so many core concepts are being
> > removed from curriculums as it's considered important for a graduate to
> > have current skills.
>
> When I studied nuclear physics, my first graduate course was a machine
> shop course.  I had to learn to operate all the machines to construct
> parts I might need in the middle of the night when experimental
> apparatus (inevitably) fails.
>
> Similarly, no computer science graduate should be able to escape
> school without learning how computers really work, and what code
> is actually generated by their compiler(s).

Unfortunately this is the case. I'm trying very hard to retain the
philosophy that this is a bad thing, rather than be thankful that it
increases my value as a professional as time goes by ;-)

> This is an excellent preface to a strong course in performance
> measurement and analysis.  How can anyone be responsible for writing
> well performing code if they don't even know what factors in their
> code affect performance?
>
> Sure, I realize that 90% of the time is spent in less than 10% of the
> code, but one must learn how to identify that 10% and apply appropriate
> techniques to improve it to achieve performance goals.

I agree. I feel though that there's more than enough people who
understand the issues to concentrate on that aspect of the code.
Indeed, it's perhaps better for these people to expend their efforts on
improving languages and virtual machines to exploit these performance
advantages than it is to hand-tune every case themselves. This way, you
can reduce the 10% to 5%

> >>There is *no* substitute for a low-level understanding of what is
> >>actually going on in a system.  Unfortunately, higher level tools tend
> >>to further obscure actual system behavior by making it more "esoteric".
> >
> >
> > I agree. I feel it's a problem we'll never really solve, only mitigate.
> > higher level tools certainly do eliminate the need for a lot of
> > low-level understanding, but as your example illustrates, it's when the
> > problems arise that low-level understanding is necessary.
> >
> > One has to ask though what an inexperienced developer was doing writing
> > process scheduler code!
>
> He wasn't inexperienced!  He had been doing OS code for several years,
> after a brilliant career in the field.  But he fell under the spell
> of "abstraction for the sake of abstraction", and began designing as
> if an OS were algebra instead of a powerful, finely tuned, throbbing
> engine that could be thrown out of balance by inattention to the
> realities of its execution.

This is certainly an area where better tools to perform analysis with
are needed.

> >>>Been there too. Time has proven it doesn't work well, and that test
> >>>driven development techniques provide more safety, and allow more
> >>>flexible forms of expression in the process, easing chafing.
> >>
> >>No argument here--test scaffolds have proven their worth many times
> >>over, yet their adoption as a standard part of any development has
> >>been widely rejected.  Maybe we're past that now...
> >
> >
> > A couple of fairly important tools, Ant (Essentially a portable "make"
> > on steroids) and JUnit (A Unit testing framework) have become massively
> > popular in the Java development arena, along with the phrase
> > "continuous integration", which more or less implies having a fully
> > automated build/test/deploy framework, to the extent that a machine on
> > the network checks out the code repository with each commit, builds it,
> > runs the entire test harness, and emails the person responsible for
> > violating a test case, should that occur.
>
> The notion of "instant regression testing" after each change is a
> powerful and fundamental idea.  I'm glad to hear that it's catching
> on!
>
> I'd like to see performance testing integrated into this scaffold,
> and that includes measuring the impact of nonlocality in distributed
> systems.
>
> It's crazy to think that a complex system can be implemented first
> and then have performance hacked into it during system test.  One
> must design for performance, and every module should be designed and
> tested to conform to a performance and resource quota that is allocated
> as a part of its specifications.  This would allow useful performance
> modelling long before a system is fully realized.

I belong to the school of thought that believes that premature
optimisation is the root of all evil. You don't know until a system is
running where the performance impediments are. Humans have proven to be
terrible at guessing where a program will run badly.

I agree that this is one of the biggest areas where tools are seriously
lacking. I also believe that the lack of these tools is one of the
biggest reasons we often fall back on languages that put these
performance concerns squarely on the shoulders of the developer, who
time and time again gets it wrong, employs less than optimal techniques
for spotting where the problems are, and wastes considerable amounts of
his own time as a result.

Too often, a decision about why something is underperforming
> > The difference that this methodology has made to system quality (not
> > necessarily code quality) and development time is difficult to describe
> > in words.
> >
> > One of the nicer side effects is it tends to free developers from the
> > 'fear' that they might break something if they decide to make
> > relatively major change, since they can easily validate the system.
> > This has given rise to a practice known as refactoring, which good
> > developers did anyway, but now has been formalised to the extent that a
> > much larger segment of the developer community have embraced it.
>
> A critical point, since so many such decisions are based on irrational
> fear--often on the part of managers.  ;-(

I feel that this 'fear' of breaking things is one of the biggest
impediments to system evolution. In the past, these fears where
actually very real, as system designs with poor modularity tend to
actually break in cryptic ways when more aggressive changes are made.

> >>The truth is that very little code needs to be really good.  If it's
> >>just 2% of all the code written, then it could all be done by 98th
> >>percentile people.  And, frankly, I don't really care whether the other
> >>98% of code is written well, or even written at all.
> >
> >
> > I agree for the most part, but there's still a lot of code out there I
> > consider essential that's utter crap. Web Browsers are a good example.
>
> Well, it's about time for three "wizards" to put together the ultimate
> web browser.  If it takes more than three, then they don't understand
> the problem well enough.

Agreed. We sorely need better browsers. This has been alleviated
somewhat of late by Mozilla firefox (A 5mb download, btw versions tens
of megabytes for IE), but there is still much work to be done.

> One cannot judge that without seeing a whole track record.  ;-)
>
> But I have known designers who spent 95% of their schedule just thinking
> and playing with little routines, then, in the last week or two, sitting
> at a keyboard completely "I/O bound", cranking out beautiful code--some
> of it in assembly language!
>
> The more common case is 50-50, but a common characteristic is that
> apparently non-productive, playful phase, when most of the good stuff
> happens.
>
> (BTW, this makes poor managers *crazy*, and can really hurt the great
> designer's next evaluation!)

I've seen this happen far too many times. I've been a victim of it
myself. Maybe one day the industry will mature to the extent that more
often it is the poor managers that get bad evaluations :-)

> Take a look at some hardware instruction counters.  The amount of code
> executed (most of it in initialization, of course) to load a program,
> create a window (with its dozens of widgets), open it, and display a
> text object, is mind numbing.  (Remember, we're talking about machines
> that can execute, conservatively, 5 million operations per millisecond.)

I was referring more to virtual machine implementations than the
(typically bloated) UI toolkits we use today. One has to ask though
what the real issue with 8mb of code is on a machine that as you say,
exectues 5 million ops per millisecond.

> I guess I don't see anything automatically noticing that creating
> and destroying timers at process dispatch time could and should be
> replaced by an interrupt-time countdown and timeout approach.

There's always going to be fringe cases where adaptable intelligence
(humans) do a better job than bulk, prebuilt intelligence. I always
remember when we applauded as a computer program defeated the world
chess master. Seldom do we apply these types of problem solving
technique to our own displine, and I think it's high time we got
started. The machines after all, are getting ridiculously fast. This
for me is an area where the use of massive parallel computing clusters
could be very interesting.

> Optimization techniques are good at little things, but terrible at
> conceptual changes.  (Come to think of it, most *people* aren't very
> good at conceptual changes, either.  ;-)

This is precisely why we shouldn't optimise ourselves into corners
early in designs. Keeping our interfaces high level, or abstract,
allows a lot of freedom down the track.

> >>In the not too distant future, we will be able to treat today's large,
> >>"nonportable" bodies of code, together with the behavioral spec of the
> >>systems they run on, as a "source language" from which we will be able
> >>to compile a program with equivalent behavior on any system we choose.
> >
> >
> > I agree that this will happen too, but it's far enough away that we
> > have to make do with intermediate solutions in the mean time. Many,
> > many years of compiler research stands in the way of such things.
> > Meanwhile people are still arguing that compiler research done in the
> > 1960's and 70's, such as using p-code machines as intermediate forms
> > along the path to better optimised solutions are a bad idea! Too
> > inefficient they say. For the most part, this is baloney. I tire of
> > issues that have been solved *years* ago continually being touted as
> > reasons to not move forward.
>
> Not really that hard.  Binary translation from one architecture to
> another has been done well for over a decade.  NASA and the phone
> companies are relying on it to replace failing old machines.

Of course, there is an obvious issue with this approach, in that we
must continue to improve the older programs in the older environments.
Indeed this is a valid approach, but you only continue it up until the
cost of replacement falls to a reasonable level. At this point, you
replace with newer programs that won't suffer the same problems as your
old ones.

> Interpretive approaches have their uses, but they must be augmented
> with native execution where it matters--but we agree on this.
>
> Imagine how much smaller system footprints could be if all the error
> handling code were kept in bytecode (since it's executed very seldom)...

Actually, Java virtual machines already do this. Exception handlers are
easily left out of the HotSpot path. I expect the Microsoft equivalents
employ the same techniques.

> I would only urge you to periodically re-evaluate the tools landscape,
> looking particularly for those that shed light on areas hidden by the
> tools you use most.  This will keep you in touch with what is *real*
> as opposed to what is merely linguistic, and that is essential in the
> long run.  Perhaps you will design the language that makes it easy for
> designers to map algorithms onto colossal distributed systems spanning
> eight orders of magnitude in bandwidth and latency!

Ironically, it was my perception of other contributors to this thread
failing to re-evalutate the landscape that inspired me to engage
heavily in this discussion. There's a very real tendancy in this
industry to write off newer tools as 'inefficient' or 'slow' based on
some very poorly thought out arguments, many of which come directly
from the marketing departments of the older, competing vendors
technologies that they support. Likewise, there are perceptions that
statically typed languages are overly constrained, when most of these
constraints went the way of the dodo with Pascal.

One must be careful within this industry (indeed any) to look beyond
the stigma's introduced in the past, and look at what is happening in
the present. Failure to do this can result in an awful lot of wasted
effort, and that's putting in mildly.

Matt