[Arrays] Random Access Times ?

[Mark P Jones]

Hi Ron,

| I tested below program with for x filled in 1 and
| 50000. And I saw that when I used 50000 it took more
| than ten times more time than when I used 1, to
| complete the expression. So much for randow access
| memory(RAM). 
| 
| Isn't there somekind of other array that really works
| with random access? 

Are you using Hugs?  That might explain your problem.  The
Hugs runtime system doesn't support allocation of variable
length structures such as arrays.  To understand why, you
should probably read my old report about the implementation
of Gofer, and you should bear in mind that Hugs has a long
history, being designed to run on (amongst other things)
8086 machines with 640K (or less) RAM.  (Historians may
recall a brief period in which variable length structures
could be allocated in a separate heap called the "flat
resource"; that, however, was removed in anticipation of a
planned Hugs/GHC merger, which never actually materialized,
but did help to prompt the development of GHCi.)

Without support for variable length structures, the original
Hugs implementation used a linked list representation as a
quick way to get support for arrays in place.  I suspect the
original implementation is still being used today.  After
all, changing it to do something a little more efficient
(e.g., using a balanced binary tree) is unlikely to be a
high priority for most people.  Hugs was designed for quick
experiments, prototyping algorithms, testing on small problems.
But there are many sources of overhead in Hugs.  It seemed
reasonable to assume that users would move to more serious
systems like GHC if they needed more serious performance.

So if your question was triggered by experiments with Hugs,
then I'd encourage you either to switch to some other system,
or else to consider replacing the Hugs implementation of
arrays with something more efficient.  (Have fun hacking C!)

And if your problem was triggered by experience with some
other system, then perhaps you could remember to mention
what you were using next time you post a question like
this :-)

All the best,
Mark