Why are strings linked lists?
Hi, can someone tell me why Haskell strings are linked lists? I have had some problems with Haskell strings: 1. Today I spend a few hours trying to track down a memory leak. It turns out I just didn't realize how much space a string takes up. On my machine "replicate 5000000 'a'" will use 90MB of space! 2. They are extremely slow for most operations like writing to disk, adding something to the end, concatenation, etc. 3. They make learning Haskell harder. Lazy IO functions like hGetContents are kind of slick in a shallow way, but I was confused about the Haskell IO model because I thought of this as the normal way IO was done, not something you could only set up through unsafeInterleaveIO or similar. Python's strings are also immutable, but they work great and are really convenient. They are apparently implemented as variable length arrays. -- Ben Escoto
G'day all. Quoting Ben Escoto <bescoto@stanford.edu>:
Hi, can someone tell me why Haskell strings are linked lists?
Because that's the way it was done in Miranda, almost 20 years ago. OK, to be fair, it does make string-to-string operations a bit more convenient. Apart from undergraduate homework exercises and some specific domains, though, this isn't exactly the "common case" of all situations where people want strings. As a matter of pure speculation, how big an impact would it have if, in the next "version" of Haskell, Strings were represented as opaque types with appropriate functions to convert to and from [Char]? Would there be rioting in the streets? Cheers, Andrew Bromage
ajb:
G'day all.
Quoting Ben Escoto <bescoto@stanford.edu>:
Hi, can someone tell me why Haskell strings are linked lists?
Because that's the way it was done in Miranda, almost 20 years ago.
OK, to be fair, it does make string-to-string operations a bit more convenient. Apart from undergraduate homework exercises and some specific domains, though, this isn't exactly the "common case" of all situations where people want strings.
As a matter of pure speculation, how big an impact would it have if, in the next "version" of Haskell, Strings were represented as opaque types with appropriate functions to convert to and from [Char]? Would there be rioting in the streets?
You could look at GHC's FastString representation (used internally). It is in $fptools/ghc/compiler/utils/FastString.lhs data FastString = FastString -- packed repr. on the heap. Int# -- unique id Int# -- length ByteArray# -- stuff Now that is pretty compact. -- Don
On Thu, Nov 27, 2003 at 10:54:11PM -0500, ajb@spamcop.net wrote:
OK, to be fair, it does make string-to-string operations a bit more convenient. Apart from undergraduate homework exercises and some specific domains, though, this isn't exactly the "common case" of all situations where people want strings.
As a matter of pure speculation, how big an impact would it have if, in the next "version" of Haskell, Strings were represented as opaque types with appropriate functions to convert to and from [Char]? Would there be rioting in the streets?
I also have wondered how much the string representation hurts haskell program performance.. Something I'd like to see (perhaps a bit less drastic) would be a String class, similar to Num so string constants would have type String a => a then we can make [Char], PackedString, and whatnot instances. It should at least make working with alternate string representations easier. John -- --------------------------------------------------------------------------- John Meacham - California Institute of Technology, Alum. - john@foo.net ---------------------------------------------------------------------------
John Meacham wrote:
ajb@spamcop.net wrote: ...
As a matter of pure speculation, how big an impact would it have if, in the next "version" of Haskell, Strings were represented as opaque types with appropriate functions to convert to and from [Char]? Would there be rioting in the streets?
I also have wondered how much the string representation hurts haskell program performance.. Something I'd like to see (perhaps a bit less drastic) would be a String class, similar to Num so string constants would have type String a => a
then we can make [Char], PackedString, and whatnot instances. It should at least make working with alternate string representations easier.
One - among many - reasons why I use Clean [[and for some years I cannot decide whether Haskell is the legitimate wife, and Clean a responsive mistress, or vice-versa...]] is that strings being unboxed arrays permit easily to communicate with lower-level binary file processing, which may be then processed by higher-level code. Thus, I can easily read and write image files (at least uncompressed, say .bmp), binary sound files, etc. There is nothing fundamental there, simply a string *is* almost directly the file buffer. Haskell introduces some overhead. I believe that the only advantage of keeping string as lists is to facilitate their lazy processing. Writing parsers and other loooong string consumers. But, as ajb said above, it can pass through a lazy conversion stage, comprehensions, etc. Jerzy Karczmarczuk Caen, France
Am Freitag, 28. November 2003 08:49 schrieb John Meacham:
[...]
I also have wondered how much the string representation hurts haskell program performance.. Something I'd like to see (perhaps a bit less drastic) would be a String class, similar to Num so string constants would have type String a => a then we can make [Char], PackedString, and whatnot instances. It should at least make working with alternate string representations easier.
I think, I have already said the following on this list. I would also like to have different character types for different subsets of Char (e.g., ASCII) and a class Character which the different character types are instances of. You could combine this idea with the string class idea in the following way: class Character c => String s c | s -> c where [...] instance Character c => String [c] c where [...] instance String PackedString Char where [...] instance String PackedASCIIString ASCIIChar where [...]
John
Wolfgang
Hi! Calling isSymbolicLink always returns False... (ghc-6.0.1linux binary tarball) It doesn't make a difference whether the symbolic link points to a regular file or a directory. Test code: #ln -s test link #ghc Test.hs -o test #./test False # Test.hs: module Main(main) where import System.Posix main = do status <- getFileStatus "link" print (isSymbolicLink status) Johannes
G'day all. Quoting Wolfgang Jeltsch <wolfgang@jeltsch.net>:
I think, I have already said the following on this list. I would also like to have different character types for different subsets of Char (e.g., ASCII) and a class Character which the different character types are instances of.
As a matter of interest, what might some of the methods of this class be? ord and chr are two obvious choices. What else? Cheers, Andrew Bromage
Am Samstag, 29. November 2003 23:58 schrieb ajb@spamcop.net:
G'day all.
Quoting Wolfgang Jeltsch <wolfgang@jeltsch.net>:
I think, I have already said the following on this list. I would also like to have different character types for different subsets of Char (e.g., ASCII) and a class Character which the different character types are instances of.
As a matter of interest, what might some of the methods of this class be? ord and chr are two obvious choices. What else?
Hello, I have such a Character class in my Seaweed library. You may have a look at http://cvs.sf.net/viewcvs.py/seaweed/code/Seaweed/Core/Characters.hs and http://cvs.sf.net/viewcvs.py/seaweed/code/Seaweed/Core/Characters/ASCII.hs The class has two methods, toCharacterMonad and fromCharacter, converting between ordinary Chars and instances of the Character class. The second function uses monads for error handling; it yields return <something> if conversion was successful and fail <something> if not. Several functions are implemented on top of these two methods. I created the Character class since I'm working with text-based network protocols and text-based file formats (like XML) where characters are often restricted to certain sets. I wanted to have such restrictions forced by the compiler. IMHO, it would be nice to also have some support for the Character class by the syntax of Haskell. I could imagine declarations of the form chartype ASCIIPrintable = ' ' .. '~' chartype ASCIICtrl = '\000' .. '\037' | '\177' A char literal like 'A' could denote not only a Char value but a value of any type which is an instance of Character. A default mechanism similar to Num could be introduced also with characters.
Cheers, Andrew Bromage
Wolfgang
G'day all. Quoting John Meacham <john@repetae.net>:
Something I'd like to see (perhaps a bit less drastic) would be a String class, similar to Num so string constants would have type String a => a
Interesting that you mention this. I've also been thinking about this lately in the context of the discussion on collections and the left-fold combinator both here and on LtU. When people say "I want String to be [Char]", what I'm actually hearing is "I want String to be a collection of Char". I may be mishearing. Cheers, Andrew Bromage
On Sat, 29 Nov 2003 ajb@spamcop.net wrote: (snip)
Interesting that you mention this. I've also been thinking about this lately in the context of the discussion on collections and the left-fold combinator both here and on LtU. When people say "I want String to be [Char]", what I'm actually hearing is "I want String to be a collection of Char". I may be mishearing.
It did strike me that it would be interesting if you could make various things instances of a List sort of class and then take, reverse, etc. would work on them. How this relates to your comment, I'm not sure. Things like map, of course, could work on unordered bags of things too, but I suppose that's what Functors are for. -- Mark
As a matter of pure speculation, how big an impact would it have if, in the next "version" of Haskell, Strings were represented as opaque types with appropriate functions to convert to and from [Char]? Would there be rioting in the streets?
For me, there would rather be celebration :), especially if these could be tuned to only use 8 bits. I tend to try to use packed strings for most of the stuff I do, but the one major problem I have with them is that there is not correspondent to hGetLine. You need to know the length of the line apriori or write your own using getting characters and concatenating them (AFAIK). Either way, you're going to get performance hits for going through [Char]s. As a minor quibble, I don't like the naming scheme with packString and unpackPS...seems very unbalanced to me :). my 2 cents - Hal -- Hal Daume III | hdaume@isi.edu "Arrest this man, he talks in maths." | www.isi.edu/~hdaume
Am Freitag, 28. November 2003 19:21 schrieb Hal Daume III:
As a matter of pure speculation, how big an impact would it have if, in the next "version" of Haskell, Strings were represented as opaque types with appropriate functions to convert to and from [Char]? Would there be rioting in the streets?
For me, there would rather be celebration :), especially if these could be tuned to only use 8 bits.
What do you mean with this? Hopefully, not dropping Unicode support because this would be a very bad idea, IMHO.
[...]
- Hal
Wolfgang
For me, there would rather be celebration :), especially if these could be tuned to only use 8 bits.
What do you mean with this? Hopefully, not dropping Unicode support because this would be a very bad idea, IMHO.
I mean to have the option of using Unicode or plain 8bit ascii as you see fit. -- Hal Daume III | hdaume@isi.edu "Arrest this man, he talks in maths." | www.isi.edu/~hdaume
Wolfgang Jeltsch wrote:
As a matter of pure speculation, how big an impact would it have if, in the next "version" of Haskell, Strings were represented as opaque types with appropriate functions to convert to and from [Char]? Would there be rioting in the streets?
For me, there would rather be celebration :), especially if these could be tuned to only use 8 bits.
What do you mean with this? Hopefully, not dropping Unicode support because this would be a very bad idea, IMHO.
What Unicode support? Simply claiming that values of type Char are Unicode characters doesn't make it so. Actually supporting Unicode would require re-implementing toUpper, toLower and the is* functions, as well as at least re-implementing the I/O library (and, realistically, re-designing it; while you *could* just force the use of a specific encoding, the result of doing so would be an I/O system which was almost worthless for real use). Right now, values of type Char are, in reality, ISO Latin-1 codepoints padded out to 4 bytes per char. It isn't possible to "drop" support which isn't there. -- Glynn Clements <glynn.clements@virgin.net>
Lennart Augustsson <lennart@augustsson.net> writes:
Glynn Clements wrote:
What Unicode support?
Simply claiming that values of type Char are Unicode characters doesn't make it so.
Just because some implementations lack toUpper etc. doesn't mean they all do.
I think the point is that for toUpper etc to be properly Unicoded, they can't simply look at a single character. IIRC, there are some characters that expand to two characters when the case is changed, and then there's titlecase and so on. toUpper etc. are AFAIK only implemented correctly for a small (but IMHO probably the useful) subset of characters.
Hbc has had those implemented for maybe 10 years.
I must admit I haven't looked at HBC -- are these functions implemented properly for codepoints >127? Outside the ISO-8859-x ranges? -kzm -- If I haven't seen further, it is by standing in the footprints of giants
ketil+haskell@ii.uib.no wrote:
What Unicode support?
Simply claiming that values of type Char are Unicode characters doesn't make it so.
Just because some implementations lack toUpper etc. doesn't mean they all do.
I think the point is that for toUpper etc to be properly Unicoded, they can't simply look at a single character. IIRC, there are some characters that expand to two characters when the case is changed, and then there's titlecase and so on.
If that was the extent of the problems, I wouldn't be describing Unicode support as "non-existent". Note that ANSI C9X doesn't handle the first problem either: 7.25.3.1.1 The towlower function #include <wctype.h> wint_t towlower(wint_t wc); 7.25.3.1.2 The towupper function #include <wctype.h> wint_t towupper(wint_t wc); And it only handles the second problemm (title case) insofar that it provides a generic transformation mechanism: 7.25.3.2 Extensible wide-character case mapping functions [#1] The functions wctrans and towctrans provide extensible wide-character mapping as well as case mapping equivalent to that performed by the functions described in the previous subclause (7.25.3.1). 7.25.3.2.1 The towctrans function #include <wctype.h> wint_t towctrans(wint_t wc, wctrans_t desc); 7.25.3.2.2 The wctrans function #include <wctype.h> wctrans_t wctrans(const char *property); Whilst a title-case transformer is the most obvious application of this, nothing in the standard specifies this.
toUpper etc. are AFAIK only implemented correctly for a small (but IMHO probably the useful) subset of characters.
Yes; so it may as well have just defined Char as an 8-bit ISO Latin-1 character. Actually, US-ASCII (i.e. the same behaviour as ANSI C with the C/POSIX locale) would arguably have been a better choice. At least that won't fail quite so badly if you use e.g. toUpper on a string which is actually in e.g. ISO Latin-2; the case may be wrong, but at least it will be the correct letter. -- Glynn Clements <glynn.clements@virgin.net>
Glynn Clements wrote:
What Unicode support?
Simply claiming that values of type Char are Unicode characters doesn't make it so.
Well, *claiming* so doesn't make it so. But actually representing characters in such a way that the Unicode conformance rules are followed, makes it so. There is no requirement for a particular API, for instance.
Just because some implementations lack toUpper etc. doesn't mean they all do.
toUpper etc. are over-rated. They are very rarely used in real life, or at least should be very rarely used, with very few exceptions: auto-titlecasing of the first word of a sentence (which I find rather handy for natural language texts), and for making "small caps" (some fonts do that internally, but that's a mistake, since it is then not language dependent). Some things that are much more interesting and of practical use are: Unicode normalisation, transformation between encoding forms (mainly for I/O), finding formal character (or rather, code point) properties, line breaking, combining character handling, language dependent collation (UCA based), decimal number parsing and formatting (for several scripts), regular expressions generalised to Unicode (including support for "default ignorable"), ... Case mapping falls rather low on the priority list. Except perhaps for the special form of "case folding" (almost lowercasing but not quite) used for IDNs, but almost only there; but could be used also for Ada, SQL, etc. that "ignore" case. B.t.w., for line breaking Thai, Lao, or Khmer, you need a dictionary. ZERO WIDTH NO BREAK SPACE can be used between words, but isn't normally.
I think the point is that for toUpper etc to be properly Unicoded, they can't simply look at a single character. IIRC, there are some characters that expand to two characters when the case is changed,
Yes, for instance for ß (sharp s). The uppercase of ß is SS. For proper lowercasing you need a dictionary. It is also language dependent. Case mapping for Lithuanian and Turkish/Azerbaijani have exceptions to what is done elsewhere. See http://www.unicode.org/Public/UNIDATA/SpecialCasing.txt /kent k
On Fri, Nov 28, 2003 at 09:21:50PM +0000, Glynn Clements wrote:
What Unicode support?
Simply claiming that values of type Char are Unicode characters doesn't make it so.
Actually supporting Unicode would require re-implementing toUpper, toLower and the is* functions, as well as at least re-implementing the I/O library (and, realistically, re-designing it; while you *could* just force the use of a specific encoding, the result of doing so would be an I/O system which was almost worthless for real use).
Right now, values of type Char are, in reality, ISO Latin-1 codepoints padded out to 4 bytes per char.
It isn't possible to "drop" support which isn't there.
I use unicode support with ghc all the time. using my CWString library and an alternate set of h* routines. Works quite well. A standard UTF8 packed string type might be handy though. John -- --------------------------------------------------------------------------- John Meacham - California Institute of Technology, Alum. - john@foo.net ---------------------------------------------------------------------------
John Meacham wrote:
What Unicode support?
Simply claiming that values of type Char are Unicode characters doesn't make it so.
Actually supporting Unicode would require re-implementing toUpper, toLower and the is* functions, as well as at least re-implementing the I/O library (and, realistically, re-designing it; while you *could* just force the use of a specific encoding, the result of doing so would be an I/O system which was almost worthless for real use).
Right now, values of type Char are, in reality, ISO Latin-1 codepoints padded out to 4 bytes per char.
It isn't possible to "drop" support which isn't there.
I use unicode support with ghc all the time. using my CWString library and an alternate set of h* routines. Works quite well. A standard UTF8 packed string type might be handy though.
IOW, you've written your own Unicode support to get around the fact that GHC doesn't provide any. Unless I'm missing something, the only "support" that GHC provides is that Char is 4 bytes. If you use Char to store anything other than ISO Latin-1 characters, none of the Haskell functions with Char in their signature will be of any use. You could just as easily have added "type WChar = Word32", and made your library use that instead of Char. -- Glynn Clements <glynn.clements@virgin.net>
In article <16327.48238.250504.185912@cerise.nosuchdomain.co.uk>, Glynn Clements <glynn.clements@virgin.net> wrote:
Simply claiming that values of type Char are Unicode characters doesn't make it so.
Actually, that's exactly what makes it so. And in article <16328.28298.217184.540118@cerise.nosuchdomain.co.uk>, Glynn Clements <glynn.clements@virgin.net> wrote:
Unless I'm missing something, the only "support" that GHC provides is that Char is 4 bytes.
No, on GHC a Char is a Unicode codepoint, which means it has only 17*2^16 possible values. This by itself is the most important aspect of Unicode support. But most of the rest is missing.
If you use Char to store anything other than ISO Latin-1 characters, none of the Haskell functions with Char in their signature will be of any use.
Actually, many of those functions ought to use Word8 instead. -- Ashley Yakeley, Seattle WA
Ashley Yakeley wrote:
Simply claiming that values of type Char are Unicode characters doesn't make it so.
Actually, that's exactly what makes it so.
Hmm. I suppose that there's some validity to that perspective. OTOH, it's one thing to state that it's true, but that's rather hollow if nothing actually behaves as if it is. It's a bit like saying "values of type Int are complex numbers; oh, BTW, the implementation is currently broken". IOW, if it walks like a duck, ...
Unless I'm missing something, the only "support" that GHC provides is that Char is 4 bytes.
No, on GHC a Char is a Unicode codepoint, which means it has only 17*2^16 possible values. This by itself is the most important aspect of Unicode support.
OK; by "Char is 4 bytes" I basically meant that it's "large enough".
But most of the rest is missing.
AFAICT, *all*[1] of the rest is missing. [1] With one rather useless exception: (maxBound :: Char) == 0x10ffff. I can't think of any other aspect of GHC's behaviour which would indicate that Char is meant to be Unicode.
If you use Char to store anything other than ISO Latin-1 characters, none of the Haskell functions with Char in their signature will be of any use.
Actually, many of those functions ought to use Word8 instead.
But then: 1. Where would you get a Char from? 2. Where would you put it? BTW, I agree that the IO functions *should* use Word8. And I really wouldn't be that bothered if the standard was changed to just use "type Char = Word8". Actually, I would prefer that to the current fiction. At least the problems with the Char functions are just implementation bugs; those functions *could* be made to work correctly. The IO problems are design bugs, and can't truly be fixed without breaking a lot of existing code. A workaround which preserves backward compatibility could result in a rather ugly interface: either all of the relevant functions use a default encoding (which will probably be the wrong one as often as not), or the "right" functions have to have their names bastardised because the "wrong" functions have already stolen the obvious names. -- Glynn Clements <glynn.clements@virgin.net>
In article <16329.12837.324931.697803@cerise.nosuchdomain.co.uk>, Glynn Clements <glynn.clements@virgin.net> wrote:
OK; by "Char is 4 bytes" I basically meant that it's "large enough".
Char is exactly the correct size. The Eq, Ord and Enum instances all work correctly. The fact that you cannot represent values outside the range is important IMO.
1. Where would you get a Char from? 2. Where would you put it?
You can convert to and from the codepoint number using toEnum and fromEnum. What is missing is UTF-8 and Latin-1 charset conversions, and character properties. You can find draft standard library code for these here: <http://sourceforge.net/projects/haskell-i18n/>
BTW, I agree that the IO functions *should* use Word8.
Right.
And I really wouldn't be that bothered if the standard was changed to just use "type Char = Word8". Actually, I would prefer that to the current fiction.
No! In GHC, a Char represents a Unicode codepoint: nothing more, and nothing less. This is something that probably ought to become part of some later Haskell standard. Frankly I find the idea that the character 'A' is somehow identical to the number 65, or octet value 65, to be completely bizarre, and Haskell does well to give them separate types. The problem is that certain IO functions do implicit Latin-1 conversion.
The IO problems are design bugs, and can't truly be fixed without breaking a lot of existing code.
Well that's what deprecation is for. New Word8-based functions would have new names. Every so often there's a burst of activity on the Libraries or the Internationalisation lists concerning this, but it never quite comes together somehow. -- Ashley Yakeley, Seattle WA
Am Freitag, 28. November 2003 22:21 schrieb Glynn Clements:
[...]
What do you mean with this? Hopefully, not dropping Unicode support because this would be a very bad idea, IMHO.
What Unicode support?
Simply claiming that values of type Char are Unicode characters doesn't make it so.
You have the possibility to store Unicode codepoints as values of type Char in GHC. This is a a little Unicode support which you don't have with 8-bit chars.
[...]
Right now, values of type Char are, in reality, ISO Latin-1 codepoints padded out to 4 bytes per char.
No, because this would mean that you wouldn't have chars with codes greater than 255 which is not the case with GHC.
[...]
But, of course, I agree with you that currently the main part of Unicode support is missing. Wolfgang
Wolfgang Jeltsch wrote:
Right now, values of type Char are, in reality, ISO Latin-1 codepoints padded out to 4 bytes per char.
No, because this would mean that you wouldn't have chars with codes greater than 255 which is not the case with GHC.
However, the behaviour of codes greater than 255 is undefined. Well, effectively undefined; I can't imagine anyone wanting to explicitly define the current behaviour, particularly the fact that: putChar c and: putChar (chr (ord c + n * 256)) are equivalent for all integral n.
But, of course, I agree with you that currently the main part of Unicode support is missing.
I think that it goes much deeper than that. Fixing the Char functions (to{Upper,Lower}, is*) is the easy part. The hard part is dealing with the legacy of the I/O "fiction", i.e. the notion that the gap (or, rather, gulf) between characters and octets can just be waved away, or at least made simple enough that it can be effectively hidden. For practical purposes, you need binary I/O, and you need I/O of text in arbitrary encodings. The correct encoding may be different for different parts of a program, and for different parts of data obtained from a single source. The correct encoding may not be known at the point that I/O occurs (at least, not for input), so you need to be able to read octets then translate them to Chars once you actually know the encoding. You also need to be able to handle data where the encoding is unknown, or which isn't correctly encoded. This isn't something which can be hidden; at least, not without reducing Haskell to a toy language (e.g. only handles UTF-8, or only handles the encoding specified by the locale etc). -- Glynn Clements <glynn.clements@virgin.net>
As a matter of pure speculation, how big an impact would it have if, in the next "version" of Haskell, Strings were represented as opaque types with appropriate functions to convert to and from [Char]? Would there be rioting in the streets?
Andrew Bromage
I would complain. I don't care much about efficiency (though it still bothers me that I don't have an answer yet to the memory leak I posted some time ago), and the easiness of dealing with strings as lists is quite important to me. Expliciting packing and unpacking would be an incovenience. Wojtek
On Sat, Nov 29, 2003 at 11:10:57AM -0500, Wojtek Moczydlowski wrote:
(though it still bothers me that I don't have an answer yet to the memory leak I posted some time ago)
If you are talking about StateT space leak, then I think I have given you an answer. My guess was that it is a CAF leak. Best regards, Tom -- .signature: Too many levels of symbolic links
Am Freitag, 28. November 2003 04:32 schrieb Ben Escoto:
Hi, can someone tell me why Haskell strings are linked lists?
I think they are lists because there is already good support for lists in Haskell. You can just take the many list functions and apply them directly to strings. You could then ask why lists are defined via an algebraic data type and not via an array type. I think, this is because algebraic data types are fundamental in Haskell and arrays are just there because of efficiency. In addition, with an algebraic data type you are able to use such nice things like pattern matching.
[...]
1. Today I spend a few hours trying to track down a memory leak. It turns out I just didn't realize how much space a string takes up. On my machine "replicate 5000000 'a'" will use 90MB of space!
You have to take into account that Chars (in GHC) take 4 bytes of memory because they denote Unicode codepoints. 5,000,000 times 4 bytes is already 20 MB. (The rest is only a constant factor. ;-))
2. They are extremely slow for most operations like writing to disk, adding something to the end, concatenation, etc.
Well, there are solutions for avoiding the quadratic time problem with concatenation like the ShowS thing in the prelude or my "EC list" implementation found under http://cvs.sourceforge.net/viewcvs.py/seaweed/code/Seaweed/Core/Lists.hs (Well, I don't know how big the overhead for building the internal data structures of EC lists is.)
3. They make learning Haskell harder. Lazy IO functions like hGetContents are kind of slick in a shallow way, but I was confused about the Haskell IO model because I thought of this as the normal way IO was done, not something you could only set up through unsafeInterleaveIO or similar.
These are problems concerning lazy I/O and not the fact that strings are implemented as linked lists.
[...]
Wolfgang
Wolfgang Jeltsch wrote: | > 1. Today I spend a few hours trying to track down a memory leak. It | > turns out I just didn't realize how much space a string takes up. | > On my machine "replicate 5000000 'a'" will use 90MB of space! | | You have to take into account that Chars (in GHC) take 4 | bytes of memory because they denote Unicode codepoints. | 5,000,000 times 4 bytes is already 20 MB. (The rest is | only a constant factor. ;-)) You have to realize that the space usage does not (necessarily) come from duplicating the character 'a'. In a lazy implementation, the representation of that character will be shared by all elements in the list. So, what is happening that there is 1 cell in the heap containing the representation of 'a', and then a linked list of length 5000000, where each element points to that cell. Just my 2 öre. /Koen
Am Freitag, 28. November 2003 12:10 schrieb Koen Claessen:
Wolfgang Jeltsch wrote: | > 1. Today I spend a few hours trying to track down a memory leak. It | > turns out I just didn't realize how much space a string takes up. | > On my machine "replicate 5000000 'a'" will use 90MB of space! | | You have to take into account that Chars (in GHC) take 4 | bytes of memory because they denote Unicode codepoints. | 5,000,000 times 4 bytes is already 20 MB. (The rest is | only a constant factor. ;-))
You have to realize that the space usage does not (necessarily) come from duplicating the character 'a'. In a lazy implementation, the representation of that character will be shared by all elements in the list.
So, what is happening that there is 1 cell in the heap containing the representation of 'a', and then a linked list of length 5000000, where each element points to that cell.
Yes, you're right. But if you choose the array alternative, you cannot use sharing and would, therefore, still need 20 MB.
Just my 2 öre.
/Koen
Wolfgang
On Fri, Nov 28, 2003 at 12:37:30PM +0100, Wolfgang Jeltsch wrote:
So, what is happening that there is 1 cell in the heap containing the representation of 'a', and then a linked list of length 5000000, where each element points to that cell.
Yes, you're right. But if you choose the array alternative, you cannot use sharing and would, therefore, still need 20 MB.
You can use sharing if you don't use unboxed arrays. Not that it matters if a character takes as much space as a pointer, but for 64-bits floating point numbers on a platform with 32-bits pointers, it would decrease memory consumption by almost half. Anyway, I'm just nitpicking. :-) -- Sebastien
On Fri, Nov 28, 2003 at 11:31:51AM +0100, Wolfgang Jeltsch wrote:
On my machine "replicate 5000000 'a'" will use 90MB of space!
You have to take into account that Chars (in GHC) take 4 bytes of memory because they denote Unicode codepoints. 5,000,000 times 4 bytes is already 20 MB. (The rest is only a constant factor. ;-))
No, in the above example there's only one single 'a' but 5000000 (:) and one [] heap-allocated cells. For example, let f = replicate 5000000 in f (f 'a') will use only about twice (and not 5000000 times) the memory of the initial example. Exactly: 10000000 * size of (:) + size of 'a' + size of []. So the only relevant thing is the list constructor (:) which needs two pointers to its arguments, and typically another pointer for housekeeping (depending on the runtime implementation). That typically makes 12 bytes per constructor (on a 32 bit architecture). Regards, Kili -- Denken ist schwer, darum urteilen die meisten. [Carl Gustav Jung]
participants (20)
-
ajb＠spamcop.net -
Ashley Yakeley -
Ben Escoto -
Bernard James POPE -
dons＠cse.unsw.edu.au -
Glynn Clements -
Hal Daume III -
Jerzy Karczmarczuk -
Johannes Goetz -
John Meacham -
Kent Karlsson -
ketil+haskell＠ii.uib.no -
Koen Claessen -
Lennart Augustsson -
Mark Carroll -
Matthias Kilian -
sebc＠macs.hw.ac.uk -
Tomasz Zielonka -
Wojtek Moczydlowski -
Wolfgang Jeltsch