Warp wrote:

>   I actually find it a bit worrying that it seems that no programming
> language introduced in the last 20 years which has got some popularity
> seems to offer any tools *whatsoever* to create memory-efficient programs
> (at least not without resorting to really ugly code which bypasses nice
> modular design).

I was about to say "Haskell" - but it's not new enough...

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

Post a reply to this message

Orchid XP v7 <voi### [at] devnull> wrote:
> Warp wrote:

> >   I actually find it a bit worrying that it seems that no programming
> > language introduced in the last 20 years which has got some popularity
> > seems to offer any tools *whatsoever* to create memory-efficient programs
> > (at least not without resorting to really ugly code which bypasses nice
> > modular design).

> I was about to say "Haskell" - but it's not new enough...

  You are telling me you can create very memory-efficient programs in
haskell without resorting to ugly low-level hacks?
  That seems to be contradictory to what I remember you saying about
those ugly arrays which can be modified in-place and such.

  OTOH, I just can't stop thinking about programming from a modular point
of view. To me a program consists of "concepts". This "concept" is some
kind of module which contains some properties, ie. members (variables,
functions...) Optimally, still from a modularity point of view, these
modules will have an *abstract* public interface (ie. one which does
not expose its internal structure).

  For example, a "pixel" is a concept. On the inside it consists, for
example, of four bytes (or four 16-bit words): The red, green, blue and
alpha components. However, from a modular point of view, these are
internal implementation details, hidden from the outside. The public
interface of this module consists of abstract functions which can be
used to manipulate its contents and behavior.

  Now, this is of course just a concept. It doesn't really exist
physically yet. When you instantiate this concept you get an "object".
You can instantiate the concept many times, getting many "objects".
All these objects can be manipulated through the abstract public
interface.

  The relevant question, from an optimization point of view, is how
much memory do these objects require? If you want to create one million
of such objects, how much memory do they require?

  In C++ you can often make it so that the objects require as much
memory as the contents of the object (eg. 4 bytes) times the number
of objects (plus a few additional bytes for book-keeping). So for
example one million of such objects could require only 4 million bytes
(plus a few bytes more). And this still while keeping the abstraction
of these objects: You still don't need to know what these objects look
in the inside. The inside of the objects doesn't need to be exposed.

  In Java this is impossible. You can't make such objects to take only
4 million bytes of memory, no matter what you do. If for the "pixels"
to take that much memory is completely imperative, what you can do is
dump the nice modular abstractions and nice public interfaces completely
and resort to very ugly hacks using integer arrays. This, of course,
causes all kinds of maintenance problems. (For example, if you would
like in the future to use 8-byte pixels instead of 4-byte ones, you are
screwed.)

  I don't have the slightest idea how all this works in Haskell, though.
Being a functional language it probably doesn't even have the concept of
"module", nor the concept of "object". Can you create "concepts" (such
as "a pixel") at all? Can you instantiate these "concepts" (and, for
example, put them inside diverse types of data containers)? Does it have
the concept of "abstraction" and "public interface" which hides
implementation details?

  If I'm not completely mistaken, in Haskell you can probably define
things like "a pixel consists of these four elements". However, that
already exposes the internal structure of a "pixel". That's asking
for maintenance trouble (because then code that uses that "pixel"
concept will assume it has those four elements, which means that it
may not be possible to modify it in the future without breaking
existing code).

  Maybe there's another completely different way of doing these things
in a functional language like Haskell? I just can't get around the
modular way of thinking about programming.

-- 
                                                          - Warp

Post a reply to this message

Warp wrote:

>   You are telling me you can create very memory-efficient programs in
> haskell without resorting to ugly low-level hacks?
>   That seems to be contradictory to what I remember you saying about
> those ugly arrays which can be modified in-place and such.

Accessing an array is no more ugly than accessing a file. (After all, 
what is a file anyway? It's a named array of bytes!) You have to use a 
monad, which makes things a bit more wordy, but that's about it.

(As I have noted before, the various array libraries are currently a 
little incomplete though...)

>   In C++ you can often make it so that the objects require as much
> memory as the contents of the object (eg. 4 bytes) times the number
> of objects (plus a few additional bytes for book-keeping). So for
> example one million of such objects could require only 4 million bytes
> (plus a few bytes more). And this still while keeping the abstraction
> of these objects: You still don't need to know what these objects look
> in the inside. The inside of the objects doesn't need to be exposed.

Short answer: Haskell can do this. But the current level of library 
support is... somewhat lacking.

[I particularly like that way that if I make an array of 4 million 
Boolean values, each one takes up exactly 1 *bit* of RAM. And yet, the 
interface is identical to any other kind of array...]

>   I don't have the slightest idea how all this works in Haskell, though.
> Being a functional language it probably doesn't even have the concept of
> "module", nor the concept of "object". Can you create "concepts" (such
> as "a pixel") at all? Can you instantiate these "concepts" (and, for
> example, put them inside diverse types of data containers)? Does it have
> the concept of "abstraction" and "public interface" which hides
> implementation details?
> 
>   If I'm not completely mistaken, in Haskell you can probably define
> things like "a pixel consists of these four elements". However, that
> already exposes the internal structure of a "pixel".

Here's the Haskell way:

Haskell has "modules". The module is the unit of abstraction in Haskell. 
When you write a module, you can define precisely what parts of it are 
visible from the outside, and which parts aren't.

Most particularly, you can make a type visible without making its 
structure visible. So you could define a Pixel type (and some functions 
for creating and manipulating Pixel values), and export the type name 
only (and the functions for working on it).

You now have a situation not disimilar to a class in Java: Only the code 
in this module knows the true implementation of Pixel. If you change 
that implementation, you'll have to change the rest of the module too, 
but any client modules will be unaffected.

So, really, it's not so different. And indeed, the standard libraries 
provide examples. There is a standard library named "Data.Set". It 
provides a type called "Set". There is a constant named "empty" which 
contains an empty set. There is a function called "insert" which takes a 
set and an item and returns a set containing that item. And so forth. 
Now, I'm *told* it's implemented with some kind of balanced tree 
algorithm, but I don't actually know. Or care. And if it changes in the 
next release of the libraries, it won't matter.

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

Post a reply to this message

> [I particularly like that way that if I make an array of 4 million 
> Boolean values, each one takes up exactly 1 *bit* of RAM. And yet, the 
> interface is identical to any other kind of array...]

C++ STL vector template class has a specialization for 'bool' that uses 
1 bit per element too. That is, a vector<bool> takes 1 bit per element.

Post a reply to this message

Orchid XP v7 <voi### [at] devnull> wrote:
> [I particularly like that way that if I make an array of 4 million 
> Boolean values, each one takes up exactly 1 *bit* of RAM. And yet, the 
> interface is identical to any other kind of array...]

  But my point was not really that. In Java you can, for example, create
an array if 32-bit integers, and each integer will take only 32 bits of
memory. That's not the problem.

  The problem in Java is that if you are making an array of *objects*,
each object having only one 32-bit integer as a member variable, there's
just no way of making each object take only 32 bits of memory.

  So you have only two options: Create a "low-level" array of integers,
which is extremely rigid and very hard to maintain (as it basically is
an array of "exposed objects"), or you create an array of abstract objects
at the cost of the memory consumption increasing by a considerable factor.

  I understand that you can create an "array of integers" or "array of
booleans" in Haskell, but that's not really what I was asking.

> Haskell has "modules". The module is the unit of abstraction in Haskell. 
> When you write a module, you can define precisely what parts of it are 
> visible from the outside, and which parts aren't.

  So Haskell is really a two-paradigm language: Functional and modular?

  (To understand what the "modular programming paradigm" means, it's
basically the same thing as the "object-oriented programming paradigm"
minus inheritance and dynamic binding.)

  Anyways, my real question was: Given such a module (eg. "a pixel"),
can you, for example, create an array of them so that each one takes
only as much memory as the sum of the sizes of its member variables?

-- 
                                                          - Warp

Post a reply to this message

Nicolas Alvarez <nic### [at] gmailisthebestcom> wrote:
> C++ STL vector template class has a specialization for 'bool' that uses 
> 1 bit per element too. That is, a vector<bool> takes 1 bit per element.

  The C++ standard library also offers the 'bitset' data container which
is specifically optimized to handle bits. (Its disadvantage is that its
size must be determined at compile time, and this size cannot change,
unline with std::vector<bool>.)

  Many operations doable to bitsets are extremely fast. (For example
counting the number of 1-bits is astonishingly fast.)

-- 
                                                          - Warp

Post a reply to this message

On Tue, 25 Mar 2008 17:34:14 +0100, Nicolas Alvarez  
<nic### [at] gmailisthebestcom> wrote:
> C++ STL vector template class has a specialization for 'bool' that uses  
> 1 bit per element too. That is, a vector<bool> takes 1 bit per element.

Yes, but that specialisation is largely considered a mistake because it  
breaks the interface associated with the generic std::vector. Also, there  
is no actual requirement that the elements occupy a single bit each; this  
is left up to the implementation.
There is std::bitset, but that does not use dynamic allocation.


-- 
FE

Post a reply to this message

> On Tue, 25 Mar 2008 17:34:14 +0100, Nicolas Alvarez 
> <nic### [at] gmailisthebestcom> wrote:
>> C++ STL vector template class has a specialization for 'bool' that 
>> uses 1 bit per element too. That is, a vector<bool> takes 1 bit per 
>> element.
> 
> Yes, but that specialisation is largely considered a mistake because it 
> breaks the interface associated with the generic std::vector.

What exactly is broken in the interface?

Post a reply to this message

On Tue, 25 Mar 2008 19:47:39 +0100, Nicolas Alvarez  
<nic### [at] gmailisthebestcom> wrote:

>> On Tue, 25 Mar 2008 17:34:14 +0100, Nicolas Alvarez  
>> <nic### [at] gmailisthebestcom> wrote:
>>> C++ STL vector template class has a specialization for 'bool' that  
>>> uses 1 bit per element too. That is, a vector<bool> takes 1 bit per  
>>> element.
>>  Yes, but that specialisation is largely considered a mistake because  
>> it breaks the interface associated with the generic std::vector.
>
> What exactly is broken in the interface?

Well, it does not satisfy the requirements of an STL container, making it  
incompatible for use with some algorithms and other containers.

For a concrete example, consider this code:

// Code begins
template < typename T >
void func()
{
	std::vector< T > v( 10 );
	T& ref = v[0];
}
// Code ends

It works with any instantiation of the generic std::vector - the standard  
guarantees it - but fails with std::vector<bool>.

Also, things like 'std::stack< bool, std::vector<bool> >' do not work  
either.

As someone else once put it: std::vector<bool>, while listed under  
"containers" in the standard, is not a container, nor does it contain  
bools.


If you really need a compact set of booleans, use std::bitset or  
boost::dynamic_bitset instead.


-- 
FE

Post a reply to this message

Warp wrote:

>> Haskell has "modules". The module is the unit of abstraction in Haskell. 
>> When you write a module, you can define precisely what parts of it are 
>> visible from the outside, and which parts aren't.
> 
>   So Haskell is really a two-paradigm language: Functional and modular?
> 
>   (To understand what the "modular programming paradigm" means, it's
> basically the same thing as the "object-oriented programming paradigm"
> minus inheritance and dynamic binding.)

If you consider "modular" to be a programming paradigm then... yes, I 
guess. (Does Pascal count as "module" too?)

Did I mention that Haskell also has "classes"? (Though they don't work 
quite the same as in OOP.)

>   Anyways, my real question was: Given such a module (eg. "a pixel"),
> can you, for example, create an array of them so that each one takes
> only as much memory as the sum of the sizes of its member variables?

You can do this. However, it's sufficiently hard work given the present 
library structure that you would only bother doing this if it was really 
necessary for your particular application.

(In future they're supposed to be adding support for transparently 
storing arbitrary types without pointer indirection. For the moment, 
you'll have to implement it yourself by hand for any type you want an 
array of.)

So it's not a language limitation, it's a library limitation. And I'm 
not sure why nobody is out fixing it, actually...

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

Post a reply to this message