[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: 6502 illegal opcodes questions

mdj wrote:

Michael J. Mahon wrote:



I expect you are largely correct.

My position is that there is no justification for putting much
energy into loyalty to *any* particular language, since *no* language
actually addresses the most pressing problem we face: explointing
relatively high degrees of parallelism in a hierarchy of connectivity.



I agree - my defense of Java in this context is (hopefully) an
objective one. Indeed there are many flaws from a performance
perspective, design perspective and some other things that are just
plain braindead in Java, but as far as I can tell, nobody here has hit
on any of the legitimate flaws. It doesn't take a lot of research to
find them either :-)



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...


OK--I like block structure, too.  ;-)

There have been numerous good ideas in language design (heck, I've even
*had* some of them ;-), but few of them could be construed as really
"significant", like the development of integrated circuits.  Language
design actually has much less effect on our ability to realize our
goals than its perpetrators generally believe.

Much of our best software efforts have been achieved using some of
our least "advanced" languages.  Making something easier does not
equate to making it better.  ;-)



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.


For over a decade I have preached to anyone who would listen that the
biggest design error in C is its use of null-terminated strings.  This
inherently insecure data representation makes unsafe programming easy
and safe programming harder.

Security demands that *all* data moves into fixed space handle the case
where the data does not fit.  Yet programmers seduced by the "cuteness"
of null-termination argue against fixing this no-brainer security lapse.

Count-prefixed strings can also be very efficiently implemented, as can
count-controlled move loops for null-terminated strings (the obvious fix
for C).



I agree completely with these points. Had this thread continued in the
C versus everything else manner it has previously I'd have got to that
one.

Ironically, null-terminated strings are less efficient than the
alternative. C programs spend a lot of time calculating the length of
string constants that were defined at compile time ;-)



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.


But it is not pointer manipulation that creates the "buffer overflow"
issue--it is uncounted data moves as a result of "terminator controlled"
loops.



Not necessarily. A common design fault in a C program is a counted
iteration over a buffer where the loop end condition was faulty
(someone picked <= instead of <, etc)

Often this results in a program appearing to run fine, until some other
loop relying on null termination fails to stop, overwriting data and
code in the process.


Um, so people should not be able to get the termination
condition for a loop wrong?  It's going to be hard to change all
those programmers' diapers, don't you think?  ;-)

BTW, I independently invented FOR i OVER <subrange type> DO ... OD
prior to ADA, so I know there are ways to simplify things--I just don't
think it's likely that anyone will be able to eliminate the possibility
of errors!

Overwriting data is a classic problem, and is usually pretty easily
found if it's literally a bad conditional or an off-by-1 error, since
the error is always misbehaving.

(Overwriting code is another matter, but code pages should be protected
from self-modification except in unusual cases.)


Pointer errors will usually show up during system testing, but string
length vulnerabilities linger long after deployment.



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.


Try implementing the multi-dimensional "plex" data structures of
Sketchpad, or implementing an efficient list processing language.
Pointers are a *real* primitive data type, as much as integers.



I would argue that any legitimate optimisation I came up with through
the use of pointer arithmetic would be to exploit the underlying
representation(s) used by the source language in question. If an
implementation exploits a certain structure of data to obtain its
efficiency, then that should be reflected in the implementation.


I didn't say anything about "pointer arithmetic" (though it can be
*very* useful to a storage allocator ;-).  I just want unrestricted
pointers so I can construct arbitrary data structures, and have the
ability to re-thread the pointers as I wish.



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.


OK, so you just want to keep guns away from children...  ;-)

My preferred approach is not to have children in the "army" in the first
place.  ;-)



Unfortunately though, this approach doesn't work in practice. The
industry is full of children :-)


Then we are accountable for the consequences.


I expect we agree that it's a matter of balance.  I'm just being a
devil's advocate for the "dangerous" tools, and the accompanying
need to be aware of implementation details, that is the source of
practically all fundamental advancement in programming models.



Of course, while machines still work they way they do, somebody has to
deal with 'dangerous' code. I have no problem with this. My issue is
the continued belief that it's necessary to use such techniques in high
level code, when it's clearly isn't.

We're still going to have C compilers for quite a while yet - and
they're useful tools for problem domains that more advanced techniques
have not been optimised for. Over time the border between where it's
appropriate and not appropriate to use a lower level tools shifts
though, and this is essentially the point.


I see where you're coming from, and I wish you luck in getting the
guns back from the children, particularly those who've developed a
fondness for shooting.  ;-)

You should take some solace from the fact that probably the most
frequently used "higher level language" is Excel, and it is completely
pointer safe.  ;-)  The only mistakes you can make in Excel are the
ones that will bankrupt your company!  (Get my point?)


It is well known that the only long-term effective way of removing old
methods from the playing field is through generational succession.  ;-)

Actually, for it to be maximally effective, though, the process of
cultural transmission of (mistaken) ideas must also be weakened.



This is what I'm doing in this thread ;-) Misinformation spread over
communication mediums like this one is a major source of said
transmission.


Hmmm.  I expect that a letter to the editor of any trade rag would
reach a much larger audience...


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.


Turing equivalence argues that there are no such examples--but there
are many examples of people's imaginations being truncated by the lack
of a concrete machine execution model.  (I cited two.)



Then the issue is a lack of understanding of the execution models used
by the newer tools, as obviously they DO have concrete execution
models.


Yes, that seems to be a problem with "high level languages"--they are
falsely advertised as "freeing their users from concern over petty
details--like how much memory is used, how many processor cycles,
and how many cache misses."  As a result, tools to determine these
critical numbers are hard to find and harder to use.

Now *there's* a common belief that needs to be stamped out!

I've generally been a bottom-up thinker (which I guess is like being
a geometer vs. an arithmetician ;-), so I've often approached questions
of performance with a blunt instrument.

For example, after implementing a compiler and getting it mostly
working, I became curious about whether it had any significant hot
spots that I could squash to get significant performance improvements.

I went to the console of the (mainframe) machine as it was compiling
itself, and manually hit the stop key a couple of dozen times, each
time writing down the program counter address.

If a part of the program was using more than 25% of the time, I should
have seen its PC value represented in my sample about 6 times, plus or
minus the square root of 6, or between 4 and 8 times.  If no range
of addresses was sampled that often, then there was no procedure in
the compiler taking at least 25% of the time.

I found a spot that was taking about a third of the time, and another
taking about a fifth, so I looked at them and sped them up by about
a factor of 4 or 5 each.

Less than an hour after taking my PC samples, the compiler was running
almost twice as fast.

Not rocket science, but thinking across several levels of abstraction--
and all I needed was a piece of paper, a pencil, and a load map for the
compiler!

(BTW, this method can be applied to *many* performance issues, but it
helped that wall clock time was identical to process time in this case.)


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.


I doubt that anyone writing a debugger or an I/O buffer manager would
agree with you--or did you lump that with hardware control?

It is an interesting exercise for a "language lawyer" to play with
formal methods to eliminate all pointers, but that doesn't make them
cease to exist any more than my closing my eyes makes the world go away.

Why should a designer be prevented from using any element that actually
exists in his designs?

Because some people cannot handle sharp objects safely, should knives
be taken off the market?

Beware of making "average" programmers more productive by limiting
the ability of superior programmers.

OK--is that enough balance?  ;-)



:-) I think the balance point is that superior programmers actually
make the same errors that average programmers do, albiet less often.
But then the superior programmer is going to be aware of this, and only
bring out the power tools when it's absolutely necessary, thus
improving the quality of his code. The tools I argue for actually
support this model. The superior programmer doesn't feel constrained,
as he has the means to switch contexts when necessary. It's the average
programmers feeling unnecessarily constrained that worries me :-)


I can buy that--just as long as someone introduces the kiddies to the
power tools at some point in their development.  In my experience,
they can get old and gray and never see a real power tool...so where
are the great programmers of the future going to be raised?


I'm also a big believer in "anihilating the problem" rather than solving
it a piece at a time.  But surely the best we can hope for from the
tools you are espousing is a reduction in the number of problems--not
the *elimination* of problems.  The argument is only quantitative, not
qualitative.



Absolutely. I'm not naive enough to believe it'll solve all problems.
Hopefully though, it'll mitigate enough of the old ones to allow us
more time to start exploring new ones. It's an evolutionary model of
course.


I sure hope so.  But, again, experience indicates that every time we
take away 50% of someone's freedom to make mistakes, we also take away
*at least* 50% of their freedom to learn something wonderful.

Remember, good judgement comes from experience, and experience comes
from poor judgement.

I'd rather see people *learn* to avoid mistakes by making them, rather
than have them "protected" from mistakes and never learning about the
law of gravity.

BTW, I don't care what languages people use once they've learned what's
what.  They will choose beautiful languates when they are appropriate
and dangerous languages when *they* are appropriate.  And if they
*haven't* learned this lesson, why should you trust them to write
code at all?

See, the world doesn't need millions of coders--it needs thousands
of *great* programmers.

There's a *reason* that we scatter broken glass around in there--but
some clown is always coming around selling thick rubber shoes, so
it's hard to keep the bozos out.  ;-)

Ever get the feeling that you may be solving a much-needed problem?  ;-)

What would happen if we provided simple programs that would allow
people to design bridges without an engineering degree?  I know that
I'd start avoiding bridges!

<rant off>  ;-)


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.


We agree about the need for abstraction.  Perhaps our disagreement is
just about whether the "floor" of our abstraction should be opaque or
transparent.

For most people, opaque floors are necessary if tall structures are to
be built--it avoids vertigo when looking down.  ;-)  But for great
designers, floors should be transparent, so that they can see the
lower-level implications of everything done at a higher level of
abstraction.  (It's their discipline that allows them to avoid
abstraction vertigo, and enables them to see the possiblity and
utility of new underlying structures.)



No no no! A great designer doesn't require transparent floors either!
He's read and comprehended the blueprints, and can tell you about the
structure with his eyes shut :-)


But what he needs to see is *not* what his models tell him is happening
below, but what is *actually* happening--that's where all the learning
happens!  That's how he grows from merely great to mega-great!

If you think you understand the behavior of a complex system, then you
are woefully misinformed.  It is time to meditate on bubbles blowing
in the wind, or the fractal nature of network traffic...


 >>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 have always maintained this pairing, even in assembly language.

It's nice when a language supports something you know is a good idea,
but you can generally do it even without explicit support.



True. It's very hard though when you drop down 2 or 3 levels of
abstraction to recreate them well, as you're ultimately implementing
poor-mans tools as you do so.


I have not often found it so.

Most often, I find that I am exploiting a pattern of behavior that
spans multiple levels of abstraction, and often couples code and data
that are surprisingly distant in conceptual space.

In most cases like this, no one looking at the high level code would
ever have imagined that there was any such relationship to be exploited.

The world of behavior is much stranger and more wonderful than our
abstract models suggest--that's what makes them "abstract".

There is enlightenment here, for those who would find it.


The only truly annoying thing is when a language obstructs you from
doing something that should be done, while making inferior approaches
easier.  (Block structure is a nice local concept, but not enough for
a robust global structure.)



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.


A practical problem, though, is that any team that newly adopts an
OO approach for a project *will* throw out their false start sometime
between 6 and 12 months down the road, and restart the project.

This is a good thing, since it is evidence of real learning, but it
strikes fear into the hearts of schedule-driven management.  ;-)
(Note my .sig line.  ;-)



Indeed. It's a growing pain that must be experienced at some point, if
progress is to be made. I'm a pretty big fan of the 'plan to throw one
away' school of thought. Often on a smaller scale single man
implementation (that I still do a lot of) I'll hack together very
quickly a prototype that solves the problem, and then once I truly
understand the issues, reimplement.


*Excellent* plan!  (Of course, the subtle part is making the prototype
real enough that all the hard parts manifest themselves.)

A related development philosophy (actually, quite bottom-up) is to
code the hardest parts of a program first--and be honest about what
they are!


Of course, this requires that you're smart enough NOT to tell your
management that this is what you've done, lest your prototype be
declared version 1.0 ;-)


Exactly!  ;-)


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.


And this is, in fact, the critical optimization for OO systems.  It will
be good when more systems actually *do* it.



JVM's have been doing this for a number of years, and with each passing
year they do it better. The .NET CLR also does it, at least if you use
a language that allows it.


Glad to hear it.  When I last looked seriously (2000), I was arguing
that the CLR should try to do this *very* well.


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.


We agree about the need for dynamic, adaptive optimization.  It's really
the only alternative in a world of separately compiled chunks of code
that wind up constituting the inner loop of applications.



Indeed. There seems to be some disagreement about what must be
sacrificed to achieve these levels of efficiency though.


Actually, almost *nothing* needs to be sacrificed if the optimization
is based on run-time truth.

All you have to do is generate a predicate that ensures that the
preconditions you have measured continue to exist prior to executing
the optimized code.  If that predicate fails, then it's time to fall
back to the original code and do some more measurement to see if a
new, perhaps more general, behavioral pattern has emerged.

Compiler technology is based on theorem proving in a fairly weak
axiom system.  You want to strengthen the axioms to allow more
theorems to be proved (optimizations to be done) statically.  But
it is not necessary to limit yourself to static knowledge, as you
know.  You can replace "proof" with "probable inference" on the
basis of observed behavior, and then generate code to verify that
this inference is still valid--or escape to the old "interpretive"
approach if it is not.  This is a much more robust system design
than one based on static proof rules, and, in fact, it largely
obsoletes the static approaches.

Of course, separate compilation of applications as *hundreds* of
separate modules already almost totally invalidates any hope of
strong axioms holding across all modules.  Better to just rely
on dynamic inference anyway.


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?


In Apollo's Domain OS, the entire library and most applications were
permanently loaded into the huge virtual address space, and could be
called across the network.  Clearly, some means of managing locality
was called for, but the functionality was there and was widely used
in the system.  The more "coarse-grain OO" the procedures were, the
better the locality/efficiency.



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.


So why haven't Kahan's upward-compatible numerics changes been made?
Could it be because some of Sun's hardware didn't support it well?
Or are the keepers of the Java spec just obstinate on this point?



It's probably a combination of obstinacy and caution. On todays
hardware, you can do some pretty amazing numerics on GPU's rather than
CPU's, which have orders of magnitude more computational power than
CPU's with regards to numerical calculations. Getting it *right* for
numerics is hard, and given the rate of change in the hardware arena
thus far, it may prove to be more sensible to have left it until the
dust settles a little.


Whoops--cop out.  There is essentially universal agreement on IEEE
FP, with the only holdouts being...LANGUAGE DESIGNERS!  It's at least
a decade past time to get with the program!

And don't worry about the GPUs and DSPs, not only are they moving to
IEEE FP as well, but their computations are practically *never* well
described in a conventional high level language, despite lots of
publicity to the contrary.

Any 2-bit (!) DSP coder can run rings around your favorite high level
language on any algorithm whose performance matters.  This will
continue to be true as long as the DSP/GPU actually has lots of
various kinds of parallelism--and for that matter, it also applies
to the various multimedia extensions (SIMD) in popular desktop
processors, as well.  The only known "solution" to this problem
is providing libraries of carefully hand-tuned code for applications
to call--and it changes radically with each generation.


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.


As the level of "primitive" invoked by an interpretive system
grows in complexity, the interpretive overhead decreases as a
fraction of execution time.

As I've already stated, however, the figure of merit I consider
important is the degree to which a tool(set) enables the exploitation
of the exploding level of concurrency supported by today's (and
tomorrow's) environment.  Sequential code efficiency, while still
important, is not the cutting edge of development.



It's important to note one obvious area of parallelism that many fail
to consider: garbage collection. In older environments where you're
forced to collect garbage yourself, you end up with your collection
being executed sequentially with your other code. While it's arguable
that this is more efficient in terms of number of cycles than collector
based approaches, you lose out on the obvious ability to collect
garbage concurrently, which on todays hardware is a big inefficiency.


Actually, in older environments, there *is* no garbage collection!

Garbage collection arises as a necessity only when programmers are
released from the obligation to return resources they are no longer
using.

Garbage collection generally means traceable data structures, and
therefore disciplined data structures.  However, don't overlook the
"catch all" discipline for garbage--simply allocating a chunk of
resource and then reclaiming everything that wasn't "registered
as persistent" at end-of-job.

In any case, concurrent garbage collection is possible in any
disciplined environment, at some level of time/space granularity
for which the discipline applies.


There's also the issue around algorithmic complexity going up with
inline collection (try implementing a fast B+ tree that doesn't leak)
so there's another big payoff to a more abstract approach.


Actually, there are a lot of good reasons not to prefer a
concurrent garbage collector, if it can be avoided.


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++.


Hmmm. This wasn't the case in 1994--or it wasn't the case in the
extant implementations...  And this comparison was done by someone
trying to do the best matrix package possible in Java.



Perhaps the implementations at the time treated multidimensional arrays
as vectors. Of course had explicit pointer arithmetic been allows we'd
have been stuck with that implementation.


No, they treated multidimensional objects as vectors of vectors of...
The workaround was to declare a one-dimensional vector of numbers, say,
and take responsibility for the multi-dimensional mapping yourself--
a much less "automatic" approach.  And pointers were not necessary,
since all the arithmetic could be index arithmetic.


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.


A major source of inefficiency without dense, multidimensional matrices,
is the inabliity to rely on simple address arithmetic to navigate a
matrix.  Introducing levels of indirection is a performance disaster.



Of course, it's simply arithmetic on an index to an ultimately
sequential structure, and treating it as multidimensional is just an
abstraction that can be implemented just as efficiently without
explicit pointers.


Of course, this explicit approach makes compiler optimization of the
element address calculations much harder to optimize.  Better to have
real multidimensional arrays.


We're in substantial agreement about this.  I've been enough on both
sides of "advocacy" that I tend to resist much of it as overstated--
both positively and negatively.

The real problems remain, and there are no silver bullets.



Absolutely. It is important in the absence of silver bullets to make
incremental improvements instead - which is more or less the approach I
advocate. Sort of a Darwinian model for software engineering if you
like.


Just be careful that the "incremental improvements" don't take the
place of the fundamental restructuring of computation that is needed
to get to the parallel future.  That would be a case of "fiddling
while Rome burns".


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 ;-)


I hear that!  ;-)

"Some of us were talking at lunch, and we hear that you've actually
seen what 'bits' are..."



LOL! Fortunately for the moment at least, the computer scientist has a
substantially smaller hierarchy to navigate in his mind than the
philospher or scientist who's trying to fathom the fabric of the
universe ;-)


Actually, not so.

I invite you to make some lists.  You will find that there are more
"levels of digital reality" than there are (known) levels of "real"
reality.

I have often opined that this is one reason that so many physicists
have found computers attractive--because their "level navigating"
skills and their understanding of invariants and conservation laws
that apply across levels is so useful.


Here we disagree.  No programmer should ever start a project without a
specific performance and resource target.  To do so is like asking an
engineer to build a bridge without specifying the span, the traffic, or
the budget!

Put another way, a programmer who doesn't understand the performance and
resource utilization consequences of his design decisions is *not* a
programmer, but a programmer's assistant.



These days, performance and resource consumption are very rarely issues
for developers to face, as the majority of projects utilise a small
fraction of the available machines.


For little problems, yes--but operating systems are not such
problems.  And neither are any programs on which people wait.

And any "little class" that someone eventually wants to call
a billion times before lunch has just become important.

In these cases, too, there is a performance model--and for "little"
or "infrequently used" code, the model suggests that performance is
not an issue--but it still needs to be examined.

I remember a case where a user wanted to write a very simple, 3-page
program to find patterns in data of a certain kind.  Since he was only
going to run it once, he didn't concern himself with resources--and
proceeded to write a quadruply-nested loop over a three dimensional
array with dimensions of 1000x1000x1000!

Needless to say, his program wouldn't even load.  But if it had
loaded, it would have run for weeks!  (Maybe now it would load if
the machine had 16GB, and then it would run in only days.  ;-)


Of course, in specific cases I agree with your approach.


I didn't think it was controversial.  ;-)


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.


For sure.  And those tools are worthless without the mindset and
training to use them.

I used to talk about the "4 T's":  targets, tools, training, and
tracking.  Leave even one of them out and you can forget about getting
a predictably performing system.



Agreed.



Of course premature *anything* is a bad idea!

But the design phase is *exactly* the right place to be concerned
with system performance.  If you design an inefficient system, then
local optimizations aren't going to get it anywhere near where a
performant design would have.



There's always the frequent issue that a problem domain is not fully
understood until you've implemented at least one solution, and realised
how little you actually understood the problem.


How true--but we've discussed that, and we seem to be on the same page.

BTW, many problems that have "formal solutions" will be revealed to
be *very* difficult when performance modelling is done.  This level
of resource modelling reveals where the formal model relies upon
"infinite" resources.  ;-)


Note that I'm talking about *high level*, structural optimization in
the design phase, not niggly bit-fiddley stuff.

Sometimes, the right approach is to make anything that could be
critical to performance have a very clean interface, so that it can
be replaced with a better one when: 1) we know how to do it, 2) there
is time, or 3) it turns out to be a big problem.



I tend to believe it's a good idea to give everything a very clean
interface. Dynamic OO languages have a clear advantage here, where
every interdependancy in a system becomes a functional one, and if you
keep your interfaces coarse, then you can achieve the approach you
outline iteratively, which is an efficiency win for implementation.


Yes, I generally agree--but there is always the problem of deciding
what level of granularity for the "modules" is appropriate.  Things
can go seriously wrong here if they are chosen either too big (structure
deficient) or too small (unaffordable overhead).  (Again, a resource
tradeoff.)

Engineering is *all about* tradeoffs.  While they are sometimes painful,
the *most* painful ones are the ones you find out later were tradeoffs
that you didn't recognize!


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.


That's why I want a "runnable" performance model of a system very
early--early enough to allow good design tradeoffs to be made.

Performance estimates can be made using many methods, some better than
others, but performance measurement is the way to go whenever it is
possible.  I'd like to see measurement/modelling done early and often.
In fact, performance testing should be a part of every regression
test scaffold.



Agreed. Hopefully soon we'll get there. Virtualisation is important
here, as different vendors will provide different levels of support for
instrumentation in their hardware and operating systems. The VM
approach offers the ability to do much of this in software.


And a compiler/code generator can do much of it with minimal support
from the OS/hardware.  Of course, it's much easier and more accurate
with hardware/OS support.


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.


True.  And an inexperienced team will often break things in hard-to-
find ways.

It takes a long track record to convince management that the design
team can accurately estimate the impact of changes, and make them.

Again, Mahon's theory of "management redshift":  "As you go up levels
of management, you are going back in time."



Absolutely true.



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 of the worst things you can do to a development team is hand them
a big pile of code to start with.  If they are a good development team,
their first act will be to burn it!  ;-)



Agreed :-)



Surely you would not defend bloat on the grounds that it is affordable?
That is why our machines are no more responsive at 3GHz than they were
at 300MHz (though they do apply Photoshop filters faster, since those
are efficient algorithms. ;-).



Is it bloat, or the fact that many of the things we do are IO bound?


It's bloat.  ;-)

More seriously, the bloat is undeniable, and is, in large part, the
reason that running much code is I/O bound--just loading the code!

In the days before we could have a gigabyte of memory, the bloat caused
lots of virtual memory I/O, which is the worst kind of I/O bound.

I think that the time required to boot a machine is an interesting
measure of performance.  Somehow, we continue to lose ground here
(and I do realize that much of that is I/O time).  Still, disk I/O
is many times faster than it was a decade ago...


I think a certain degree of bloat is unavoidable, hopefully it evolves
out of systems over time.


That would be a new evolutionary trend.  ;-)

Organisms usually get simpler only when some extreme stressor hits their
environment.  Hand-cranked machines?  Boot times exceeding attention
spans?  ;-)


The only schema that I can see approaching this level of structural
optimization would be an aggressive genetic algorithm--and all the
computers on the planet may not yet be quite enough to do the job
in a reasonable amount of time.  Later...  ;-)



It may not ever be possible, given the raising complexity of software.
If the software we run can challenge the best machines, we'll never
have enough horsepower to evolve solutions...


Here's a heuristic to apply...a solution should get more complex only
if the problem it is solving gets more complex.  By this rule, there
is some other factor besides problem complexity that is driving up
solution complexity.  I think that it is because we have erroneously
concluded that complexity has no intrinsic cost, so we can increase
it with impunity.

Perhaps this error is abetted by the hope that new tools will increase
our ability to cope with any negative consequences of complexity.  ;-)

This can't be good for survival...


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.


Yes, but "structural" decisions about the decomposition of the problem
must be made to proceed, and they should be made in a framework of
performance and resource tradeoffs, just as much as schedule and
budget tradeoffs.

Just because you decided not to decide doesn't mean you didn't make
a decision.  ;-)



Indeed. I believe though that minimising these decisions through
keeping interfaces highly abstract is the best way to provide space
down the track for optimisation. Generally speaking, it isn't that hard
to get it right, but getting everyone to agree is oft problematic :-)


Hence the need for objective models, and the expertise to appreciate
their results.


Actually, they are long past the point of "improving" anything.  All
the people that understood those programs or the environments used to
create them are long gone.  These are truly "legacy" apps, in the sense
that they are treated just like gears or bolts--taken completely for
granted until something fails.



There are always fringe cases, that's for sure.



I agree with your points, Matt.  But consider how much of the resistance
you describe may be generated by *overselling* the "new" thing as the
"solution to all our problems".  Successfully marketing new approaches
requires subtlety (which I apparently lack ;-).



Indeed the overselling of the new is as much to blame as overselling
the old. The massive hype around OO is a testament to this.


Well, "one hand washes the other", they say.  So the overselling will
increase to match the perceived resistance to change.  Then the "echoes"
of the overselling constitute the basis for the next wave of resistance
to the *next* change.  Sounds like a setup for "deja vu all over again".

-michael

Parallel computing for 8-bit Apple II's!
Home page:  http://members.aol.com/MJMahon/

"The wastebasket is our most important design
tool--and it is seriously underused."