dons:

ndmitchell:

...

Hi

(All these results are from GHC 6.9.20071226, but suspect they hold for 6.9.* and 6.8)

The following code:

test = head "neil"

Produces (with -O2):

Text.HTML.TagSoup.Development.Sample.test = case GHC.Base.unpackCString# "neil" of wild_aaU { [] -> GHC.List.badHead @ GHC.Base.Char; : x_aaY ds1_aaZ -> x_aaY }

However:

test = head ['n','e','i','l']

Produces:

Text.HTML.TagSoup.Development.Sample.test = GHC.Base.C# 'n'

The packing of the string has damaged the optimisation. Is there anyway to mitigate this? I ideally want to do this in RULES to derive an efficient parser from a set of parser combinators, and the unpackCString# really gets in the way of future optimisations.

I could imagine adding two rules to the simplifier:

case unpackCString# "" of ==> case [] of case unpackCString# "xyz" of ==> case (C# 'x': unpackCString# "yz") of

Then the simplifier could recover the optimised version.

The first case makes sense, and is just a RULE. Though it seems GHC already does this?

g = head ""

goes to:

M.g = badHead @ Char

without prompting.

Now, ByteString uses a rule relating to unpackCString#:

{-# RULES "ByteString pack/packAddress" forall s . pack (unpackCString# s) = inlinePerformIO (B.unsafePackAddress s) #-}

So I wondered if I could write a rule for head/unpackCString

{-# OPTIONS -fglasgow-exts #-}

module M where

import GHC.Base

-- ^ enable rewrite rules {-# RULES "head/string literal" forall s . head (unpackCString# s) = case s of ""# -> head [] _ -> C# (indexCharArray# (unsafeCoerce# s) 0#) #-}

f = head "neil"

Urgh. not what we want though. GHC won't index the string at compile time, and I can't write a RULE for it.

I was surprised to note we can actually match on unboxed string literals in rules, but then the question is how to recover the nice list structure again.

As the string has already been packed for us, this seems a bit hard. Otherwise a unpack (pack s) rule could be used.

Perhaps you can newtype Char and use string overloading to work around the packing issue?

This goes back to an old gripe of mine actually -- we can't get at the length of a C string literal at compile time either, which would be super useful in rules. If we had some light primitives for this, that GHC new about (head#, length#), that accessed the internal data about what strings are up to, that could be useful. -- Don

On Mon, Apr 28, 2008 at 02:00:38PM -0700, Donald Bruce Stewart wrote:

This goes back to an old gripe of mine actually -- we can't get at the length of a C string literal at compile time either, which would be super useful in rules.

I think that this is easy to do by, instead of desugaring "foo" -> unpackCString# "foo"# desugaring "foo" -> unpackCStringLen# 3# "foo"# where unpackCStringLen# _ = unpackCString# It's not really feasible to do head#, tail# etc this way, though, so if head#/tail# are done another way then it's probably best to do length# that way too. By the way, please do file tickets for the issues from this thread, so that the issues and ideas don't get forgotten about! Thanks Ian

Hi

The first case makes sense, and is just a RULE. Though it seems GHC already does this?

g = head ""

goes to:

M.g = badHead @ Char

without prompting.

Nope, as far as I can tell "" gets translated to [], not unpackCString# "" - hence the unpack never gets in the way. If you had the second rule, you'd soon want the first.

So I wondered if I could write a rule for head/unpackCString

Urgh. not what we want though. GHC won't index the string at compile time, and I can't write a RULE for it.

Yeah, I tried that too...

Perhaps you can newtype Char and use string overloading to work around the packing issue?

That would work on GHC, but not on Hugs. Thanks Neil

Hi

...

That would work on GHC, but not on Hugs.

Optimisation and Hugs don't go together anyway.

I want the code to work on Hugs, and perform fast on GHC. As it turns out, for this particular application, Hugs is faster than GHCi by about 25%. Thanks Neil

Hi

Optimisation and ghci don't go together, so I don't know what your point is there.

It's very worth having the application work in both Hugs and GHCi, and its not always GHC=faster, only if you compile it - so you trade your compile time for your run time. A delicate balance, with more than one local optima.

Anyway, its the same with ByteString -- we have it work in ghci or hugs or nhc, but its only worth actually optimising for GHC.

Can you use overloaded Strings with Hugs? I am not aware of how to. I am happy to use RULES's and pragmas etc, but I can't see a way of doing overloaded strings this way, as by the time I've got to RULES I've gained the unpackCString, which just won't go away! Thanks Neil

Hi

You'd have to conditionally use overloaded strings in GHC only. I'm not sure it would work ( can you quantify the cost of not being able to take head at compile time? )

The cost of not having this is probably ~10x slower for the tagsoup library :-( - i.e. pretty huge. I'm looking at other ways of doing this, perhaps using a preprocessor or something - which would be more robust than RULES and perhaps generalise in other nice ways. Thanks Neil

Hi

what is general purpose stuff. I don't think there is anything wrong with magic for primitive types, but if there is a useful general-purpose mechanism trying to get out, let's liberate it.

I think the tension comes from representing String's as CString's, not actual lists of Char and (:). If the simple representation was used, then things like case on a known constructor would deal with a lot of these cases. However, for String, its probably too expensive in terms of compile time and compile memory to keep the unpacked representation.

But I'd like a clear spec first.

PROPOSAL 1: Add the following rules to the simplifier:

case unpackCString# "" of ==> case [] of case unpackCString# "xyz" of ==> case (C# 'x': unpackCString# "yz") of

Pros: Doesn't introduce any new API or other long-term maintenance issues. A necessity for certain optimisations. Cons: Makes the simplifier slightly more complex - but I hope not by much! PROPOSAL 2: Add some primitives and hard-coded simplifications: (I'm giving an example with length#, but I imagine head#, tail#, null# and some others would also be handy) Add the following in GHC.<somewhere> length# :: CString -> Int {-# RULE "length/string" forall xs . length (unpackCString xs) = length# xs #-} Add the rules to the simplifier: length# "string" = <the result> Pros: length "haskell" becomes a compile-time constant. Very useful for the ByteString people. Makes RULES and CString interact better, with better optimisation possibilities. Cons: Requires defining a small API and maintaining it. Requires more work to the simplifier, but still should be fairly self-contained. Cries out for a generalisation (but I don't think there is a good one). SUMMARY: I think Proposal 1 is a really good idea, with a little effort and a lot of return. I think Proposal 2 is more effort than proposal 1, with probably less return - but may still be worth it. I think Don will really want Proposal 2. Thanks Neil

| > PROPOSAL 1: Add the following rules to the simplifier: | > | > > case unpackCString# "" of ==> case [] of | > > case unpackCString# "xyz" of ==> case (C# 'x': unpackCString# "yz") of | | I've been wanting to have a go at hacking GHC for a while, and this | seems like a good candidate to start with. If there is no obvious | reason this is a bad idea, I'll try and provide a patch and some | benchmarks/measurements in about a month. That sounds great! Please let's have a chat before you sail in -- I have a good idea where to put this. Simon

Hi

...

Cons: Makes the simplifier slightly more complex - but I hope not by much!

And it doesn't work for my case -- I'd really want length as a compile time constant.

Could you elaborate on what kind of rules you think we could write with the ability to get the head?

One of my ideas was some RULES that expand: test x | "neil" `isPrefixOf` x = ... | "ned" `isPrefixOf` x = ... And obtains direct pattern-matching code. I have a lazy continuation-based parsing library which could use this extensively. See my other ongoing thread on this mailing list for more details of where this is going.

The rule I'd like to write is:

"pack/packAddress" pack (unpackCString addr) = ByteString (length# xs) 0 addr

That requires Proposal 2, so needs to have an API defined -- including length# and some others. Out of curiosity, how much performance boost would this give in ByteString?

That sounds great! Please let's have a chat before you sail in -- I have a good idea where to put this.

Simon: I will email you in a couple of weeks to discuss it. Thanks Neil

On Tue, Apr 29, 2008 at 8:44 PM, Don Stewart wrote:

ndmitchell:

...

That requires Proposal 2, so needs to have an API defined -- including length# and some others. Out of curiosity, how much performance boost would this give in ByteString?

It matters for programs with lots of constant strings. HAppS' webserver reported good speedups doing this translation by hand.

I imagine that my HTTP parser library would also get a nice boost from this. -- Johan