Warp wrote:

>   The advantages of an array are:
> 
> 1) It's the most memory-efficient data container possible.

Yup. In Haskell you'd have a tiny amount of overhead (like, a few 
pointers), but for large arrays, this is insignifigant.

> 2) Accessing an element of the array is fast, as you have random access.
> You can access any array in O(1), and moreover the constant factor
> involved is very small.

Indeed. And since an array is so small, and contiguous in memory, it's 
highly likely that big chunks of it will be in your cache hierachy. (Not 
so for, say, linked lists, which tend to be scattered around all over 
the place.) You can also "prefetch" arrays, and so forth.

> 3) Elements in an array are in contiguous memory locations. This fact is
> often dismissed in higher-level languages, but sometimes used to one's
> advantage in lower-level languages, sometimes for great speedups.
> 
>   The reason why this property can sometimes be used for speed is that
> small array elements can be handled in bigger bunches (usually word-sized)
> because they are all in contiguous memory locations. For example doing
> certain operations to a byte string can be done 4 or 8 bytes at a time
> (getting almost that much speedup) with low-level tricks.

I would think particularly copying an array or some subset of it could 
be done in big batches (IIRC, the IA32 arch even has special opcodes for 
this), regardless of the notional size of the element type.

>   Of course arrays have their disadvantages, which is the reason why other
> types of data containers exist in the first place.

Sure.

>> One nice touch is that an unboxed array of Bool actually uses 1 bit per 
>> element. The library automatically handles all the bit twiddling 
>> operations required to pack 8 Bools into one byte, and unpack them again 
>> later. (I wonder if the C++ STL can do that?)
> 
>   std::vector<bool> uses one bit per element.

OK.

>   OTOH this actually causes more trouble than it's worth, as it makes
> std::vector behave in certain cases rather differently when the element
> type is bool compared to any other element type. This is a common complaint.

...because C++ "bool" is actually some mannar of integer?

>   boost::dynamic_bitset is an incredibly efficient data container for
> individual bits. For example it can count the number of set bits in the
> entire container at something like 0.5 clock cycles per bit in my computer.

Haskell is seemingly improving all the time, but it's still got a way to 
go. The stuff people have targetted their efforts at are quite fast, but 
some less-interesting parts are unexpectedly slow. (E.g., the various 
rounding functions are rather slow. They work by turning a Double into 
an approximate propper fraction and then converting that to an integer - 
or something equally absurd...)

-- 
http://blog.orphi.me.uk/
http://www.zazzle.com/MathematicalOrchid*

Post a reply to this message