(Yes, another long post that nobody is going to actually read...)



So a while back, I mentioned that Haskell has a veritable zoo of array 
libraries, and it's all a bit of a mess. Some of you may be wondering 
what the problem is. After all, BASIC has arrays. Pascal has arrays. C 
has arrays. Java has arrays. And they're all pretty simple. So why the 
drama?



First of all, in any of the above languages, if you want to store 
several items of data, an array is usually the first data structure you 
reach for. It's simple, it's built-in, it's always there, it's 
moderately efficient, and it's "good enough" to start with. Maybe at 
some point you'll decide that what you "really" want is actually a 
hashtable, or a balanced tree, or maybe something even more fancy. But, 
initially, an array is an easy way to go.

In Haskell, the default container of choice is of course a list. (When a 
Haskeller says "list", they generally mean "single-linked list".) It's 
built-in, it's always there, and there's a huge library of list 
processing functions. The Haskell Standard Prelude (a library which is 
always imported by default unless you explicitly ask not to) contains 53 
list-related functions, and the standard List library contains an 
additional 51 functions for a total of 104 list-processing functions.

By contrast, the standard Haskell 98 arrays library defines a piffling 
12 functions for dealing with arrays. And that's *it*.

Lists are simple Algebraic Data Types (ADTs). They are hard-wired into 
the compiler, but only to allow syntax sugar. If you forgo the sugar, 
it's quite trivial to implement your own list type:

   data List x = Node x (List x) | End

It is then a simple beginner's exercise to define all of the standard 
list processing functions from first principles:

   head (Node x xs) = x
   tail (Node x xs) = xs

   length End = 0
   length (Node x xs) = 1 + length xs

   sum End = 0
   sum (Node x xs) = x + sum xs

   map fn End = End
   map fn (Node x xs) = Node (fn x) (map fn xs)

   ...etc...

You will find Haskell tutorials which paint this picture. It is true 
that defining the list processing functions in a maximally efficient way 
is a touch tricky - but defining them such that they merely *work* is 
child's play. It's a common beginner's exercise in understanding Haskell.

Lists have another nice property. Haskell is a "lazy" language. If you 
call a function, the function call isn't really executed until you try 
to "examine" the result. And even then, the call might not be executed 
completely, but only far enough to generate the part of the data you're 
looking at. In Haskell, data doesn't literally "exist" until you 
"inspect" it - much like Schroder's famous undead cat.

What all of this means is that you can construct "infinite" lists. These 
lists are notionally of infinite length, but so long as you only 
"examine" a finite portion of the list, only that finite portion will be 
constructed (which uses finite time and space). In this way, you can 
seperate the code for generating the data from the code that decides how 
much data to generate - and we programmers all know that seperating 
things is usually a good idea.



Lists are simple recursive ADTs. And we can make infinite lists. Trees 
are simple recursive ADTs too. And they can be infinite. (Although in 
practice this isn't as useful.)

Arrays are not recursive, and they're not ADTs either. Support for 
arrays must therefore be hard-wired into the compiler. (Unlike lists and 
trees which can be defined in plain Haskell.) But this is no different 
to any other programming language.

More irritatingly, arrays can't "grow" or "shrink". Their size is preset 
when allocated. (You can, of course, construct a slightly more 
sophisticated container that allocates a large array and keeps track of 
how much of it is "occupied". But there isn't a standard library for 
this.) If you want to process an array to construct a new array, you 
have to do potentially extra work to determine how large the result is, 
or waste space allocating an array that's larger than necessary.

This, again, is a problem for any programming language. But Haskell has 
some particular problems of its own.

Most particularly, the Haskell language is fundamentally based upon the 
idea that data never, ever changes. If you want to "change" the contents 
of a list, what you actually do is make a new, altered *copy* of that 
list. The original list still exists and is unaltered. In the common 
case that the old list isn't being used anywhere, the garbage collector 
(GC) will remove it.

For a list, that means that altering the Nth element of the list causes 
all N-1 elements before it to be copied. Any elements *after* the Nth 
one can be shared between the new list and the old list.

Similarly, for a tree, modifying a leaf node means making a new leaf 
node plus the roughly log(N) parent nodes of that node. All other leaves 
and branches can be shared between the two trees. Which is usually 
fairly efficient.

By contrast, to alter one element of an array, you must copy THE ENTIRE 
ARRAY. If the array is large, this is obviously absurdly inefficient in 
both time and space.

In summary:

        | random read | random write |
-------+-------------+--------------+
List   | X           | X            |
Tree   | log X       | log X        |
Array  | 1           | Y            |

(Approximate number of operations to access element X in a container 
holding Y elements.)

Copying a large array is probably a lot faster than copying a large 
linked list (better cache performance, possibly CPU-specific fast copy 
instructions), but even so, arrays look horribly slow for writing. While 
such arrays can still be used as lookup tables, all the algorithms that 
depend on O(1) array updates are suddenly infeasibly slow.



Haskell has the ability to read and write files on disk. And what is a 
file? Why, it's an array of bytes. GHC, everybody's favourit Haskell 
compiler, provides the ability to use *mutable* arrays, using the same 
facility used for I/O - that is, monads. Using these arrays, we get O(1) 
read *and* O(1) write access.

This, you would think, would be the end of the story. But not so.

Both Haskell 98 immutable arrays and GHC's mutable arrays try to be too 
fancy. Instead of using numbers of indicies like any normal programming 
language, they allow arbitrary objects to be used (so long as the 
programmer supplies a way to convert them to integers). This has two 
results:

- Arrays need not be zero-origin. They can be one-origin, or even 
twelve-origin.

- Multidimensional arrays are implemented by using tuples are indicies.

Array indicies are always checked at runtime. There is no way to disable 
this check. There is also no way to directly use the underlying "real" 
indicies.

Amusingly, somebody discovered that by getting the "convert object to 
index" code wrong, you could make your Haskell programs segfault. Even 
though they contain only pure Haskell code. Obviously, this should 
never, ever happen, for any reason. The library was quickly changed. Now 
instead of checking the index object against the index bounds, the index 
object is converted to a real index and then checked. This means that 
now the original index object can be out of bounds, causing 
multidimensional arrays to "wrap around" at the ends in an 
implementation-dependent way.

You'd think they could get this stuff right, eh?

The obvious course of action would be to expose a lower-level interface 
to arrays, using plain integers for indicies (and offering a way to 
bypass runtime bounds checks), and then build higher-level libraries on 
top of that. But noooo...



I should also point out that the mutable and immutable arrays above are 
both "boxed" arrays. That is, an array of *pointers* to data, rather 
than literally an array of data itself. (Rather like a Java array of any 
object type.)

GHC also offers "unboxed" arrays, which work more like C arrays. 
However, these are only offered for certain element types. (Int, Double, 
etc.) Theoretically you can add more - but it's not terribly easy (or 
documented).

Still, using unboxed arrays brings several advantages:

- Uses less RAM.

- The GC can treat the whole array as "one object", so GC workload is 
reduced.

- Probably gives much better cache behaviour than an array of pointers 
pointing all over the place.

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

A non-obvious side effect of this is that the elements of such an array 
*cannot* be as-yet unexecuted function calls. Unboxed arrays are 
therefore *strict*. That is, "examining" any element of the array causes 
the *entire* array to be computed, not just that element (as would be 
the case for a normal boxed array or a list).



So, GHC gives you arrays with are immutable, mutable, boxed or unboxed. 
Use whatever you fancy. That, surely, should be the end of the story. 
Right??

Well... actually no. For a couple of reasons:

- The silly array indicies (and the inability to get round them).

- The array libraries provide only very basic, simplistic 
functionallity, compared to the sophisticated list and tree libraries.

- Using a monad is typically not very convinient. Thus, we would like to 
have arrays that "look like" lists or something, but have the efficiency 
of arrays.

Hence the zoo of other array libraries out there. Allow me to survey a 
few of them...



First came the Bytestring library. Now Haskell 98 defines a type called 
"String", but this is really just an alias for a linked list of (32-bit 
Unicode) characters. That means that the entire list-processing library 
can be brought to bear on all your string-processing problems. But it's 
also not especially efficient.

[One paper claims that each character in the list takes up 12 *bytes* of 
RAM. Not to mention that, say, a 1,000 character string gives the GC 
1,001 tiny objects to process. And, obviously, you can forget about 
cache coherance. And then there's the O(n) random access time.]

To summarise: Flexible, not very fast.

Enter the Bytestring library. It provides a type called "Bytestring", 
and a bunch of functions for working with them each are mostly carbon 
copies of the standard list-processing functions. However, a Bytestring 
is actually a linked list of array "chunks", and each such chunk can 
contain up to 256 bytes. [These bytes can be interpretted either as 
8-bit unsigned integers, or as 8-bit character codes.]

This representation has the following effects:

- Memory usage goes from 12 bytes per character to (approximately) 1 
byte per character.

- Random access is now 256 times faster.

- The GC now has 256 times fewer "objects" to consider.

- When doing I/O, the Bytestring chunk can be directly used as the I/O 
"buffer" in the low-level OS calls. There is no need to "pack" or 
"unpack" the byte array that the OS uses to/from Haskell list nodes.

On top of that, Bytestrings can be "sliced". That is, two Bytestring 
objects can refer to different portions of the same underlying array 
chunk(s). And *that* means that the library can offer a function that 
takes a Bytestring and returns a new Bytestring with the initial 
character removed - in O(1) time and space.

Since Bytestrings are linked lists, they also support very fast 
concatenation operations too. In short, Bytestring is able to provide a 
list-like API with efficiency equal or superior to lists.

Bottom line: Take your string-processing program, import Bytestring, 
change a few type signatures and function names, and watch your program 
go several orders of magnitude faster (and use less RAM). On top of 
that, you now have reasonably fast random access over strings too 
(assuming they aren't really huge).

Bytestring is great. Bytestring is good. Bytestring makes everything 
warm and fuzzy. However, Bytestring only works for... well... bytes. 
It's great for fast I/O. It's great for processing raw binary or raw 
text. But it's not a general-purpose array; it can only store bytes.



And then along came GHC 6.10.1. This comes with a technology preview of 
the Data Parallel Haskell (DPH) library which has been in development 
for the last few years.

DPH provides a new kind of array: "parallel arrays". A parallel array is 
immutable, unboxed, and therefore strict. That is, "examining" any 
element of a parallel array causes the entire array to be computed.

In parallel.

The DPH framework runs off the back of a small stack of brick-thick 
research papers describing how to take the Haskell source code and 
radically rearrange both the physical data layout in RAM and the order 
of operations in the program to expose maximum opportunity for parallel 
execution. The work is automatically sliced up into appropriate-size 
chunks, and fired off to seperate CPU cores.

For example, in plain Haskell you can represent a vector as a list. You 
can then take the dot product of two such vectors using

   dot xs ys = sum [ x * y | x <- xs | y <- ys ]

If you now trivially modify this code to say

   dotp xs ys = sumP [: x * y | x <- xs | y <- ys :]

then the "vectors" are now parallel arrays, the multiplications will be 
performed in parallel, and the sum will also be parallelised as much as 
possible.

One of the Big Features is that the stuff you do in parallel can itself 
be parallel - they call it Nested Data Parallelism (NDP). And it's very 
hard to implement efficiently. The engine does things like storing an 
array of pairs as a pair of arrays, and storing an array of arrays as a 
single flat array with an array of subarray indicies. (This allows the 
flat array to be corsely split into chunks for processing on each core, 
even if some of the logical subarrays are tiny while others are huge.)

Most if not all of this would be impossible in a "normal" programming 
language, becuase you could (trivially) write code where the order of 
execution matters. This kind of thing works so well in Haskell because 
you *cannot* write such code. (Although, clearly, you could design a 
library like this for another language and say "and if the order 
matters, your program will break". Only Haskell gives you a guarantee 
though.)

It's very exciting stuff, and it's brand-new, hot off the press... but 
it isn't finished yet. Half the code is missing. Documentation? What 
documentation? You also have to seriously contort your program to get it 
to work. (The compiler support isn't finished yet, so you can't mix 
parallel and sequential code in the same module, for example.)

It'll be awesome when it's finished, but for now it's not very useful.



And then there's more libraries - vector, uvector, storablevector, etc. 
These address perceived weaknesses of the other array libraries. So we 
have various array libraries, each with a different overlapping set of 
features and deficiencies.

To give you a flavour, let's take a look at the "vector" library. This 
provides "vectors" which are really just arrays again. (They're called 
something different to prevent name clashes, basically.) They're boxed, 
and come in mutable and immutable flavours. But, unlike what GHC itself 
provides, there's no silly indicies here.

Of course, they had to go one better and try to make their immutable 
arrays as fast as mutable ones. Basically, using a bunch of clever 
trickery, they get the compiler to do in-place updates wherever 
possible, even through the programmer thinks they're using plain old 
immutable arrays. I can't say how well it works, but the technology is 
pretty interesting...

To begin at the beginning, in Haskell is it very common to write 
"pipelines" of list-processing functions such as

   filter odd . map head . group . sort

[That reads from right to left. So, sort some stuff, group it, map over 
it, and finally filter it.]

On paper, each of those functions consumes a list and constructs a new 
list. Which isn't terribly efficient. Hence various compilers and 
libraries attempt to perform "fusion". That is, we want these seperate 
functions to "fuse" together into one big loop that traverses the input 
list once, directly building the output list, with no intermediate 
temporary lists and no repeated traversals.

Of course, this isn't always possible (e.g., how do you sort a list in 
one pass?), but ideally that's what we'd like. We want the compiler to 
take our pipeline of seperate functions and build one giant, 
custom-tuned loop out of it. (We could, of course, code that loop 
ourselves directly. But if the compiler can do it automatically, that 
would be much better!)

One of the most recent fusion techniques is "stream fusion". It involves 
a "stream" type which can be processed non-recursively. So our pipeline 
above becomes something like

   stream_to_list . filter_stream odd  . list_to_stream .
   stream_to_list .    map_stream head . list_to_stream .
   stream_to_list .  group_stream      . list_to_stream .
   stream_to_list .   sort_stream      . list_to_stream

So, instead of processing a list, you turn that list into a stream, 
process the stream, and turn the stream back into a list. Which, 
obviously, is more work. But it turns out that only stream_to_list is 
recursive; the rest is completely non-recursive, with no looping at all. 
Also, it should be perfectly obvious that

   list_to_stream . stream_to_list

does nothing. [Not 100% true, not close enough.] So we can delete the 
repeated conversions, leaving

   stream_to_list . filter_stream odd  .
                  .    map_stream head .
                  .  group_stream      .
                  .   sort_stream      . list_to_stream

In other words, convert the list to a stream, perform multiple 
(non-recursive) stream-processing operations on the stream, and then 
convert the stream back into a list. stream_to_list contains the only 
actual loop here, so when all the definitions are inlined, we get one 
huge loop at the end of it all, as required. (Although I suspect in 
reality, you can't actually implement the sort_stream function.)

Stream fusion is great for lists, but it works for any data structure. A 
"stream" is really just a traversal of a data structure. xxx_to_stream 
sucks data out of a container, and stream_to_xxx squirts that data into 
a new container. So you can, for example, apply stream fusion to arrays. 
And the vector library does this.

However, if you just want map, filter, sum, etc., why are you using 
arrays? Lists can already do that! No, the only reason to use an array 
is if you want *random access*. And stream fusion can't help you with that.

Some clever soul has come up with "array recycling" though. This is 
basically a flashy term for a system that performs as many updates as 
possible in-place rather than making copies. It works together with 
stream fusion, and uses a similar approach:

Functions that update arrays are split into several smaller, more 
primitive functions. There's a function that allocates new space, a 
function that copies the existing data into the new space, and a 
function that updates the new array. By using clever rewrite rules, you 
can get it so that if you update an array, and then immediately update 
it again, there's no need to copy the array. You can just perform all 
updates bar the initial one in-place.

The result? Immutable, referentially-transparent arrays with almost the 
same performance as mutable arrays. (All these clever transformations 
happen at compile-time, not runtime.)

...and now, the C programmers must be chuckling to themselves that 
Haskell is doing all this work where a C programmer would just trivially 
use a mutable array in the first place. :-P But while I doubt it will 
ever be possible to write Haskell code that runs faster than C, being 
able to write high-level, maintainable code that still performs close to 
C would be a big win, IMHO. C can *always* be made slightly faster 
somehow; the question, to me, is how much effort it takes to make fast 
code in C vs Haskell.

(If DPH ever gets into a working state, being able to trivially write 
highly parallel code in Haskell should become a C-killer feature. But 
let's wait until that one actually happens...)

TO BE CONTINUED...

Post a reply to this message

Invisible wrote:
> (Yes, another long post that nobody is going to actually read...)

Ok, in this case you're right... That'd be long even as a blog post!

Post a reply to this message

Nicolas Alvarez wrote:
> Invisible wrote:
>> (Yes, another long post that nobody is going to actually read...)
> 
> Ok, in this case you're right... That'd be long even as a blog post!

Damn - good thing I left out all the *technical* detail I wanted to 
include. ;-)

Post a reply to this message

Wrong newsgroup.  Please use p.ot.f.h.b.b.b  :P

Post a reply to this message

Kyle wrote:
> Wrong newsgroup.  Please use p.ot.f.h.b.b.b  :P

Or, alternatively, just stop writing about Haskell. I mean, it's not 
like anybody is interested in my ramblings or anything... :-S

Post a reply to this message

"Invisible" <voi### [at] devnull> wrote in message 
news:49b69614$1@news.povray.org...
> Kyle wrote:
>> Wrong newsgroup.  Please use p.ot.f.h.b.b.b  :P
>
> Or, alternatively, just stop writing about Haskell. I mean, it's not like 
> anybody is interested in my ramblings or anything... :-S

Sometimes it just feels good to write stuff down, even if you know noone 
will ever read it.  So don't stop just because no one seems interested, only 
stop if you don't like doing it anymore.

Linguistic question: 'noone' or 'no one'? 'noone' seems wrong somehow :-/ :)

cu!
-- 
#macro G(b,e)b+(e-b)*C/50#end#macro _(b,e,k,l)#local C=0;#while(C<50)
sphere{G(b,e)+3*z.1pigment{rgb G(k,l)}finish{ambient 1}}#local C=C+1;
#end#end _(y-x,y,x,x+y)_(y,-x-y,x+y,y)_(-x-y,-y,y,y+z)_(-y,y,y+z,x+y)
_(0x+y.5+y/2x)_(0x-y.5+y/2x)            // ZK http://www.povplace.com

Post a reply to this message

Zeger Knaepen wrote:
> Linguistic question: 'noone' or 'no one'? 'noone' seems wrong somehow :-/ :)


I use "noone" in such a manner occasionally, but I don't really know if 
it is correct or not.  I think not, but it sounds kinda cool.  ;-)

Two grammatical errors that have been getting under my skin lately are:

1) People using the word "loose" when what they really mean is "lose". 
I read this a few moments ago, "...with all the people loosing their 
jobs...", and cringed yet again.

2) People misusing the word "myself" where they should be using "I", 
such as, "A friend and myself went...".  Grrr again!

Post a reply to this message

Invisible wrote:
> Lists have another nice property. Haskell is a "lazy" language. If you 
> call a function, the function call isn't really executed until you try 
> to "examine" the result.

That's another thing Python 3.x does now. Lots of new "iteration" features 
(where "iteration" means "for loop" basically), with iterator objects that 
calculate the next element on the fly instead of (for example) taking all 
the keys from a big dictionary and putting them in a list to iterate over. 
One more reason to drop Tcl in favor of Python. :-)

> By contrast, to alter one element of an array, you must copy THE ENTIRE 
> ARRAY. If the array is large, this is obviously absurdly inefficient in 
> both time and space.

You know, there are lots of situations where something *like* an array can 
be made more efficient, and tunable. For example, you can have an array with 
an exception list, where you first look up the index in the exception list, 
and if it isn't there, you look it up in the main body, and copy the main 
body to a new one when the exception list gets too long. IIRC, it's O(1) 
with a much larger constant and a bit of wasted space. Obviously if you're 
going to do something where you change every element of the array, you might 
want a different structure also.

> (I wonder if the C++ STL can do that?)

I think that's why you can have a template plus versions of the code 
specific to particular types. In Ada, you just say "Packed array" instead of 
"array" and it's automatic for whatever size (like, 12-bit FAT records, for 
example).

> First came the Bytestring library. Now Haskell 98 defines a type called 
> "String", but this is really just an alias for a linked list of (32-bit 
> Unicode) characters. That means that the entire list-processing library 
> can be brought to bear on all your string-processing problems. But it's 
> also not especially efficient.

Sounds like what Erlang does. Strings are linked lists of integers 
(converted by the output formatting code). You also have "array of bytes" 
type strings, mostly used for protocol stuff (packing bytes into a protocol) 
but which can be used as strings. Erlang, unfortunately, doesn't really 
support unicode, so the linked-list-of-integers really only works with the 
rest of the system when all the integers are <256.  D'oh!

> The result? Immutable, referentially-transparent arrays with almost the 
> same performance as mutable arrays. (All these clever transformations 
> happen at compile-time, not runtime.)

Yah, Erlang special-cases certain updates that are common idioms (since 
records/structs are basically immutable arrays in Erlang) and folds them up 
in a similar way. Not at the source level, tho. Not as a library, but as a 
compiler wart. :-)

-- 
   Darren New, San Diego CA, USA (PST)
   My fortune cookie said, "You will soon be
   unable to read this, even at arm's length."

Post a reply to this message

Kyle wrote:
> 1) People using the word "loose" when what they really mean is "lose". I 

I do that a lot because "Loose/lose" is backwards from "Choose/chose". I 
always have to look it up, even when I think I've finally memorized it.

> 2) People misusing the word "myself" where they should be using "I", 
> such as, "A friend and myself went...".  Grrr again!

Or "I" instead of "me."

"They were talking to a friend and I, and they said..."

-- 
   Darren New, San Diego CA, USA (PST)
   My fortune cookie said, "You will soon be
   unable to read this, even at arm's length."

Post a reply to this message

Invisible <voi### [at] devnull> wrote:
> First of all, in any of the above languages, if you want to store 
> several items of data, an array is usually the first data structure you 
> reach for. It's simple, it's built-in, it's always there, it's 
> moderately efficient, and it's "good enough" to start with.

  The advantages of an array are:

1) It's the most memory-efficient data container possible. Not one single
bit of ancillary data is used per element. All elements are packed in
memory as tightly as possible (well, at least if the size of the element
is a multiple of the natural (half-)word size of the target architecture,
or the element has the size of one byte).

  You can pack certain type of elements even more efficiently than that
when using special data containers, for example radix trees, but even
then you'll have to put the container data inside an array if you want
to beat the memory usage of the "raw" array. In other words, you will
still be using an array (rather than some other data structure), even if
interpreting the contents of the array is a bit more complicated.

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 (in the order of 1 clock cycle if the element
happens to be in the fastest cache; and even if there's a cache miss,
it will still usually be faster than accessing elements in other non-array
data containers).

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.

  There are many algorithms which are very efficient and fast to perform
on arrays, while inefficient or difficult to do for other types of data
containers (such as linked lists).

  Of course arrays have their disadvantages, which is the reason why other
types of data containers exist in the first place. For example, removing one
element from the middle of the array is a slow operation, while for example
for a linked list it's very fast (assuming you have a handle to the element
to be removed). Adding elements to an array while constantly keeping it sorted
is inefficient, while with other data containers (eg. a balanced binary tree)
it's efficient. Arrays are not very dynamic, and trying to make them dynamic
(while still maintaining efficiency) usually causes overallocation and/or
memory fragmentation.

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

  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.

  The suggested solution is to use a separate, efficient data container for
bit-sized booleans. boost::dynamic_bitset is such a container, and it has
often been suggested to be included in the next C++ standard, and the
std::vector<bool> converted to a 1-byte-per-element container.

  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.

-- 
                                                          - Warp

Post a reply to this message

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

On Tue, 10 Mar 2009 21:08:05 +0100, Orchid XP v8 <voi### [at] devnull> wrote:
> Warp wrote:
>>   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?

No, because std::vector<bool> is specialised in such a way that:
  1 - It is not a container (not as the C++ standard defines them)
  2 - It does not actually contain values of type 'bool'

It is one of those things that seemed like a good idea at the time, but  
did not turn out so good in practice.


-- 
FE

Post a reply to this message

> On Tue, 10 Mar 2009 21:08:05 +0100, Orchid XP v8 <voi### [at] devnull> wrote:
> > ...because C++ "bool" is actually some mannar of integer?

  The main problem is that you can't have a pointer pointing to an
individual bit. The smallest element to which a pointer can point is
a byte.

  However, in a std::vector<bool> you have 8 bools per byte, and you can't
create a pointer (or reference) which will point to one of them. This
makes std::vector<bool> behave inconsistently compared to a std::vector
of any other type.

  You can index a std::vector<bool> in the regular way, and you can even
assign values to these indexed elements. In other words, you can do this:

std::vector<bool> boolVec(100, false);
boolVec[50] = true; // Works ok

  However, since operator[] cannot return a true reference to the indexed
bool (because there can't be a reference to an individual bit), what it
returns is a proxy object which behaves like if it was a reference to the
individual bit. Thus it almost looks like std::vector<bool> behaves like
any other vector.

  However, since operator[] for bool vectors does not return a reference
of type bool, you can't do something like this:

bool& boolRef = boolVec[50];

  That will simply fail. The same would work for any type other than bool.

  References and pointers to vector elements are used quite a lot in
practical C++, so this makes std::vector<bool> inconsistent and less
usable than it could be.

  Since it's rare in practice that one would need a huge std::vector<bool>
(if what you really need is a huge bitset, then boost::dynamic_bitset is
by far a better choice, as it's more versatile and efficient), it can be
argued that making std::vector<bool> special was a design mistake.

  It has been suggested that std::vector<bool> would instead allocate
one byte per element because bytes can be addressed, and this would make
it consistent. It would probably also make it more efficient speedwise.

Fredrik Eriksson <fe79}--at--{yahoo}--dot--{com> wrote:
> No, because std::vector<bool> is specialised in such a way that:
>   1 - It is not a container (not as the C++ standard defines them)

  I'm not really sure what you mean by that.

  std::vector<bool> works mostly like any other container. The only thing
it cannot do is give you an address to an individual element. Too bad that's
a cumbersome limitation in some cases.

-- 
                                                          - Warp

Post a reply to this message

Invisible wrote:
> Kyle wrote:
>> Wrong newsgroup.  Please use p.ot.f.h.b.b.b  :P
> 
> Or, alternatively, just stop writing about Haskell. I mean, it's not
> like anybody is interested in my ramblings or anything... :-S

Blog.

Post a reply to this message

On Tue, 10 Mar 2009 23:41:00 +0100, Warp <war### [at] tagpovrayorg> wrote:
> Fredrik Eriksson <fe79}--at--{yahoo}--dot--{com> wrote:
>> No, because std::vector<bool> is specialised in such a way that:
>>   1 - It is not a container (not as the C++ standard defines them)
>
>   I'm not really sure what you mean by that.
>
>   std::vector<bool> works mostly like any other container. The only thing
> it cannot do is give you an address to an individual element. Too bad  
> that's a cumbersome limitation in some cases.

You described the reasons yourself higher up in your post. The C++  
standard describes the requirements for "container" types (section 23.1),  
and std::vector<bool> does not satisfy them.


-- 
FE

Post a reply to this message

>>> Wrong newsgroup.  Please use p.ot.f.h.b.b.b  :P
>> Or, alternatively, just stop writing about Haskell. I mean, it's not
>> like anybody is interested in my ramblings or anything... :-S
> 
> Blog.

Heh. Nobody reads that either...

Post a reply to this message

>>> ...because C++ "bool" is actually some mannar of integer?
> 
>   The main problem is that you can't have a pointer pointing to an
> individual bit. The smallest element to which a pointer can point is
> a byte.

Ah, I see.

Post a reply to this message

>>>> Wrong newsgroup.  Please use p.ot.f.h.b.b.b  :P
>>> Or, alternatively, just stop writing about Haskell. I mean, it's not
>>> like anybody is interested in my ramblings or anything... :-S
>> 
>> Blog.
> 
> Heh. Nobody reads that either...

Did you see that MS is paying for a full ride for a PHD
at Strathclyde in Glasgow researching Haskell numeric
indexing? Pay is the key word there. They intend the 
code to end up in GHC, perhaps as optimizations for
parallel threads. You should apply for this Andrew,
it has to be better than where you are working. If you
make them happy I bet you could end up working for MS.

Post a reply to this message

Tim Attwood wrote:

> Did you see that MS is paying for a full ride for a PHD
> at Strathclyde in Glasgow researching Haskell numeric
> indexing?

http://personal.cis.strath.ac.uk/~conor/phds/

No, I missed the announcement.

> Pay is the key word there. They intend the code to end up in 
> GHC, perhaps as optimizations for
> parallel threads. You should apply for this Andrew,
> it has to be better than where you are working. If you
> make them happy I bet you could end up working for MS.

Heh, well it can't hurt to ask...

(Where the hell is "strathclyde" though? Or Glasgow for that matter... 
Time for Google Maps!)

Post a reply to this message

On Wed, 11 Mar 2009 09:49:16 +0000, Invisible <voi### [at] devnull> wrote:

>
>(Where the hell is "strathclyde" though? Or Glasgow for that matter... 
>Time for Google Maps!)

Hey Jimmie, does yer mither sew...  :-)

It's where I was born and everyone sounds like me only not so posh ;)

PS it is in Scotland.
-- 

Regards
     Stephen

Post a reply to this message

>> (Where the hell is "strathclyde" though? Or Glasgow for that matter... 
>> Time for Google Maps!)
> 
> Hey Jimmie, does yer mither sew...  :-)

WTF-O-Meter: 2.8

> PS it is in Scotland.

Ah.

So... pretty expensive then? :-P

Post a reply to this message

On Wed, 11 Mar 2009 10:16:52 +0000, Invisible <voi### [at] devnull> wrote:

>>> (Where the hell is "strathclyde" though? Or Glasgow for that matter... 
>>> Time for Google Maps!)
>> 
>> Hey Jimmie, does yer mither sew...  :-)
>
>WTF-O-Meter: 2.8
>

A traditional greeting amongst young men.


>> PS it is in Scotland.
>
>Ah.
>
>So... pretty expensive then? :-P

Hard for me to say

http://www.gcal.ac.uk/student/money/managing/living.html
-- 

Regards
     Stephen

Post a reply to this message

On Wed, 11 Mar 2009 09:08:19 +0000, Invisible wrote:

>>>> Wrong newsgroup.  Please use p.ot.f.h.b.b.b  :P
>>> Or, alternatively, just stop writing about Haskell. I mean, it's not
>>> like anybody is interested in my ramblings or anything... :-S
>> 
>> Blog.
> 
> Heh. Nobody reads that either...

Wrong.

We've been over this before, just because nobody replies doesn't mean 
nobody is reading.

I refuse to be "nobody" and I read your blog, when you decide to update 
it.

Jim

Post a reply to this message

On Wed, 11 Mar 2009 10:16:52 +0000, Invisible wrote:

>>> (Where the hell is "strathclyde" though? Or Glasgow for that matter...
>>> Time for Google Maps!)
>> 
>> Hey Jimmie, does yer mither sew...  :-)
> 
> WTF-O-Meter: 2.8
> 
>> PS it is in Scotland.
> 
> Ah.
> 
> So... pretty expensive then? :-P

If it's paid, then the cost isn't your problem.

Jim

Post a reply to this message

>>> PS it is in Scotland.
>> Ah.
>>
>> So... pretty expensive then? :-P
> 
> If it's paid, then the cost isn't your problem.

Depends on how much they pay.

Post a reply to this message

On Wed, 11 Mar 2009 16:35:34 +0000, Invisible wrote:

>>>> PS it is in Scotland.
>>> Ah.
>>>
>>> So... pretty expensive then? :-P
>> 
>> If it's paid, then the cost isn't your problem.
> 
> Depends on how much they pay.

Fair point.  Knowing the cost of living gives you something you can 
negotiate from.

Jim

Post a reply to this message

Tim Attwood wrote:

> Did you see that MS is paying for a full ride for a PHD
> at Strathclyde in Glasgow researching Haskell numeric
> indexing? Pay is the key word there. They intend the code to end up in 
> GHC, perhaps as optimizations for
> parallel threads. You should apply for this Andrew,
> it has to be better than where you are working. If you
> make them happy I bet you could end up working for MS.

Well, I emailled the guy making the announcement. Now we wait...

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

Post a reply to this message

> (Yes, another long post that nobody is going to actually read...)

I read it all actually when you first posted, but didn't feel I had anything 
to contribute, apart from letting you know I read it to make you feel better 
:-)

Post a reply to this message

Invisible wrote:
> TO BE CONTINUED...

http://www.bash.org/?121126

-- 
   Darren New, San Diego CA, USA (PST)
   My fortune cookie said, "You will soon be
   unable to read this, even at arm's length."

Post a reply to this message