Containers and strictness

Ben midfield at gmail.com
Fri Jun 25 02:24:10 EDT 2010


whoops, didn't see ticket 3999.

http://hackage.haskell.org/trac/ghc/ticket/3999

is this going into containers?

ben

On Thu, Jun 24, 2010 at 11:02 PM, Ben <midfield at gmail.com> wrote:
> this all sounds like wonderful work, looking forward to it.
>
> slightly off topic, but in whatever revision of Data.IntMap you come
> up with, can you include foldrWithKey, toDescList, mapAccumRWithKey
> and the rest of the reverse-order traversals which are in Data.Map?
> all for consistency.....
>
> best regards, ben
>
> On Thu, Jun 24, 2010 at 9:00 AM,  <libraries-request at haskell.org> wrote:
>> Send Libraries mailing list submissions to
>>        libraries at haskell.org
>>
>> To subscribe or unsubscribe via the World Wide Web, visit
>>        http://www.haskell.org/mailman/listinfo/libraries
>> or, via email, send a message with subject or body 'help' to
>>        libraries-request at haskell.org
>>
>> You can reach the person managing the list at
>>        libraries-owner at haskell.org
>>
>> When replying, please edit your Subject line so it is more specific
>> than "Re: Contents of Libraries digest..."
>>
>>
>> Today's Topics:
>>
>>   1. Re: Containers and strictness (Edward Kmett)
>>   2. Re: Containers and strictness (Johan Tibell)
>>
>>
>> ----------------------------------------------------------------------
>>
>> Message: 1
>> Date: Thu, 24 Jun 2010 09:28:15 -0400
>> From: Edward Kmett <ekmett at gmail.com>
>> Subject: Re: Containers and strictness
>> To: Johan Tibell <johan.tibell at gmail.com>
>> Cc: Duncan Coutts <duncan.coutts at googlemail.com>,
>>        libraries at haskell.org
>> Message-ID:
>>        <AANLkTim3-EIxn7fLIybNqXXR0tEZznitJlPG-78IdHN7 at mail.gmail.com>
>> Content-Type: text/plain; charset="utf-8"
>>
>> On Thu, Jun 24, 2010 at 8:27 AM, Johan Tibell <johan.tibell at gmail.com>wrote:
>>
>>> On Thu, Jun 24, 2010 at 1:59 PM, Edward Kmett <ekmett at gmail.com> wrote:
>>>
>>>>
>>>>
>>>> 2010/6/24 Milan Straka <fox at ucw.cz>
>>>>
>>>> > On 24 June 2010 11:14, Milan Straka <fox at ucw.cz> wrote:
>>>>> >
>>>>> > > I need some opinion:
>>>>> > >
>>>>> > > - Do you think methods like insert/lookup/delete/etc should be strict
>>>>> in
>>>>> > >  key/element?
>>>>> > >
>>>>> > >  As Claus wrote, right now it is undocumented and inconsistent (both
>>>>> in
>>>>> > >  the methods of one container and also in the same methods of
>>>>> different
>>>>> > >  container).
>>>>> >
>>>>> > Just as it is sometimes important to be able to do strict inserts, it
>>>>> > is important sometimes that we have maps that are lazy in the
>>>>> > elements. There are important use cases both ways.
>>>>> >
>>>>> > So yes we should have some kind of consistent convention. We could do
>>>>> > worse than the naming convention where the strict versions use a
>>>>> > trailing prime ' character.
>>>>>
>>>>> I thought we are talking only about keys/elements. I would leave the
>>>>> values untouched.
>>>>>
>>>>> Personally I vote for:
>>>>> - keys in Maps and elements in Sets are strict
>>>>> - vales in Maps are left untouched (lazy)
>>>>>
>>>>
>>>> +1 from me
>>>>
>>>> Great work so far.
>>>>
>>>
>>> The space overhead per key/value pair is 6 words (48 bytes on a 64-bit
>>> architecture) when using lazy values but only 4 words (32 bytes) per
>>> key/value pair when using strict (unpacked) values, a 50% difference. This
>>> really starts to matter with big enough data sets (as seen in the recent
>>> Twitter analysis thread). When work with Big Data it's often desirable to
>>> fit as much data in RAM as possible as the result of many algorithms (think
>>> machine learning or search ranking) differs with the amount of data you can
>>> hold in memory.
>>>
>>> Something to consider.
>>>
>>
>> I definitely agree that unboxing can help a great deal with performance and
>> space utilization.
>>
>> However, as containers does not currently require any exotic extensions, I
>> think that perhaps a type family -based generic map would belong in another
>> 'unboxed-containers' or 'adaptive-containers' package (both of which
>> currently exist on hackage), as it dramatically extends the language
>> extension footprint of containers, taking it from something that easily runs
>> across a wide array of Haskell implementations to something very
>> ghc-specific.
>>
>> -Edward Kmett
>> -------------- next part --------------
>> An HTML attachment was scrubbed...
>> URL: http://www.haskell.org/pipermail/libraries/attachments/20100624/de037f10/attachment-0001.html
>>
>> ------------------------------
>>
>> Message: 2
>> Date: Thu, 24 Jun 2010 15:39:52 +0200
>> From: Johan Tibell <johan.tibell at gmail.com>
>> Subject: Re: Containers and strictness
>> To: Edward Kmett <ekmett at gmail.com>
>> Cc: Duncan Coutts <duncan.coutts at googlemail.com>,
>>        libraries at haskell.org
>> Message-ID:
>>        <AANLkTilS6-78NRFcTFaXc9HmnWcr5zCGiAi7awa0ohsU at mail.gmail.com>
>> Content-Type: text/plain; charset="iso-8859-1"
>>
>> On Thu, Jun 24, 2010 at 3:28 PM, Edward Kmett <ekmett at gmail.com> wrote:
>>
>>> I definitely agree that unboxing can help a great deal with performance and
>>> space utilization.
>>>
>>> However, as containers does not currently require any exotic extensions, I
>>> think that perhaps a type family -based generic map would belong in another
>>> 'unboxed-containers' or 'adaptive-containers' package (both of which
>>> currently exist on hackage), as it dramatically extends the language
>>> extension footprint of containers, taking it from something that easily runs
>>> across a wide array of Haskell implementations to something very
>>> ghc-specific.
>>>
>>
>> Good point. I plan to look into such a library this summer. Any
>> non-strictness related API improvements to the containers package (e.g.
>> strict folds) should carry over to a new, adaptable containers package.
>>
>> -- Johan
>> -------------- next part --------------
>> An HTML attachment was scrubbed...
>> URL: http://www.haskell.org/pipermail/libraries/attachments/20100624/7f796de2/attachment-0001.html
>>
>> ------------------------------
>>
>> _______________________________________________
>> Libraries mailing list
>> Libraries at haskell.org
>> http://www.haskell.org/mailman/listinfo/libraries
>>
>>
>> End of Libraries Digest, Vol 82, Issue 22
>> *****************************************
>>
>


More information about the Libraries mailing list