slow performance on big strings

[mwotton]

I tried encoding a large-ish string (40k bytes) and started getting timeouts. Looking into it, I think you might have a quadratic algorithm hidden in there?

     initialWriter.basics            Data.Text.Punycode.Encode          376           1    0.0    0.0     0.0    0.0
       encode                        Data.Text.Punycode.Encode          324           0    0.0    0.0    97.6   98.3
        initialWriter.b              Data.Text.Punycode.Encode          331          11    0.0    0.0     0.0    0.0
        initialWriter                Data.Text.Punycode.Encode          326          11    0.7    0.7    97.6   98.3
         inner3                      Data.Text.Punycode.Encode          332          47    0.0    0.0    96.7   97.5
          inner3.helper              Data.Text.Punycode.Encode          333          47   35.6   47.3    96.7   97.5
           delta                     Data.Text.Punycode.Encode          420          36    0.0    0.0     0.0    0.0
           n                         Data.Text.Punycode.Encode          419          36    0.0    0.0     0.0    0.0
           inner3.helper.delta'      Data.Text.Punycode.Encode          394          37    0.0    0.0     0.0    0.0
            delta                    Data.Text.Punycode.Encode          395          37    0.0    0.0     0.0    0.0
           inner3.helper.n'          Data.Text.Punycode.Encode          390          37    0.0    0.0     0.0    0.0
            n                        Data.Text.Punycode.Encode          391          37    0.0    0.0     0.0    0.0
           inner3.helper.m           Data.Text.Punycode.Encode          389          37    4.5    0.4     4.5    0.4
           inner2                    Data.Text.Punycode.Encode          385     1339068   14.3   22.5    56.5   49.7
            inner2.helper            Data.Text.Punycode.Encode          386     1339068   25.9   24.9    42.3   27.2
             adapt                   Data.Text.Punycode.Shared          411         142    0.0    0.0     0.2    0.0
              adapt.helper           Data.Text.Punycode.Shared          413           0    0.2    0.0     0.2    0.0
               adapt.loop            Data.Text.Punycode.Shared          415         243    0.0    0.0     0.0    0.0
             adapt.helper            Data.Text.Punycode.Shared          410         142    0.0    0.0     0.0    0.0
             adapt.helper.delta'     Data.Text.Punycode.Shared          409         142    0.0    0.0     0.0    0.0
             inner2.helper.h'        Data.Text.Punycode.Encode          408         142    0.0    0.0     0.0    0.0
             h                       Data.Text.Punycode.Encode          407         285    0.0    0.0     0.0    0.0
             baseToAscii             Data.Text.Punycode.Encode          406         143    0.0    0.0     0.0    0.0
             inner                   Data.Text.Punycode.Encode          401         435    0.5    0.0     0.5    0.0
              baseToAscii            Data.Text.Punycode.Encode          404         292    0.0    0.0     0.0    0.0
              inner.t                Data.Text.Punycode.Encode          402         435    0.0    0.0     0.0    0.0
             inner2.helper.bias'     Data.Text.Punycode.Encode          399         143    0.0    0.0     0.0    0.0
             bias                    Data.Text.Punycode.Encode          398         143    0.0    0.0     0.0    0.0
             inner2.helper.delta'    Data.Text.Punycode.Encode          392     1339068   15.7    2.3    15.7    2.3
              inner2.helper.delta'.d Data.Text.Punycode.Encode          396     1336928    0.0    0.0     0.0    0.0
              delta                  Data.Text.Punycode.Encode          393     1339068    0.0    0.0     0.0    0.0
             inner2.helper.n'        Data.Text.Punycode.Encode          388     1339068    0.0    0.0     0.0    0.0
             n                       Data.Text.Punycode.Encode          387     1339068    0.0    0.0     0.0    0.0
           inner3.helper.h'          Data.Text.Punycode.Encode          335          47    0.0    0.0     0.0    0.0
           h                         Data.Text.Punycode.Encode          334          47    0.0    0.0     0.0    0.0
         initialWriter.basics        Data.Text.Punycode.Encode          327           0    0.2    0.2     0.2    0.2
          isBasic                    Data.Text.Punycode.Shared          329           0    0.0    0.0     0.0    0.0
        initialWriter.basics         Data.Text.Punycode.Encode          325          11    0.0    0.0     0.0    0.0
      encode                         Data.Text.Punycode.Encode          359           0    0.0    0.0     0.0    0.0
       initialWriter.b               Data.Text.Punycode.Encode          364          46    0.0    0.0     0.0    0.0
       initialWriter                 Data.Text.Punycode.Encode          361          46    0.0    0.0     0.0    0.0
        inner3                       Data.Text.Punycode.Encode          365          46    0.0    0.0     0.0    0.0
         inner3.helper               Data.Text.Punycode.Encode          366          46    0.0    0.0     0.0    0.0
          inner3.helper.h'           Data.Text.Punycode.Encode          368          46    0.0    0.0     0.0    0.0
          h                          Data.Text.Punycode.Encode          367          46    0.0    0.0     0.0    0.0
        initialWriter.basics         Data.Text.Punycode.Encode          362           0    0.0    0.0     0.0    0.0
       initialWriter.basics          Data.Text.Punycode.Encode          360          46    0.0    0.0     0.0    0.0

[Cipherwraith]

I made a patch to fix the memory leaks in encode. Please try it:

#3