String operation idiomatic : Better Go string performance or enhance mutable string

[ziyu_huang]

I wonder where will be the way to Go in "enhance string operation"
performance.
In Go the string seems just work, there is not much performance fine
tune. So, if you do some string operation, you will see it's much
slower compare to Java or Python.

So, will Go enhance string ? Or Go will adopt another approach for
enhance string operation ?

I think we can treat bytes.Buffer as a kind of Mutable string. But it
lacks a lot of string function provide in strings package or compare
to Python.

If Go author want to enhance string operation. I will vote to enhance
bytes.Buffer.
It will be much easy to understand or to extend functionality of
mutable instead of immutable string.
(in java, string performance is on the hand of VM, I can't do much
about it).

Here is my study code

//use Buffer as mutable string
buf := bytes.NewBuffer(make([]byte,0, 10));
fmt.Printf("buff cap='%d', s='%s'\n", cap(buf.Bytes()), buf.Bytes
()); //empty string
println("** operate a buffer as writer");
fmt.Fprintf(buf, "a buffer");
fmt.Printf("buff cap='%d', s='%s'\n", cap(buf.Bytes()), buf.Bytes
());
println("** run out of capacity, buff do auto-resize");
fmt.Fprintf(buf, ", operate like mutable string");
fmt.Printf("buff cap='%d', s='%s'\n", cap(buf.Bytes()), buf.Bytes
());
println("** truncate the string");
buf.Truncate(10);
fmt.Printf("buff cap='%d', s='%s'\n", cap(buf.Bytes()), buf.Bytes
());
println("** truncate also mean 'expand'");
buf.Truncate(15);
fmt.Printf("buff cap='%d', s='%s'\n", cap(buf.Bytes()), buf.Bytes
());
println("** reset the string");
buf.Reset();
fmt.Printf("buff cap='%d', s='%s'\n", cap(buf.Bytes()), buf.Bytes
());
println("** write a string...");
buf.WriteString("write a string...");
fmt.Printf("buff cap='%d', s='%s'\n", cap(buf.Bytes()), buf.Bytes
());
println("** read 5 bytes...");
buf.Read(make([]byte, 5));
fmt.Printf("buff cap='%d', s='%s'\n", cap(buf.Bytes()), buf.Bytes
());

execute result:
buff cap='10', s=''
** operate a buffer as writer
buff cap='10', s='a buffer'
** run out of capacity, buff do auto-resize
buff cap='49', s='a buffer, operate like mutable string'
** truncate the string
buff cap='49', s='a buffer, '
** truncate also mean 'expand'
buff cap='49', s='a buffer, opera'
** reset the string
buff cap='49', s=''
** write a string...
buff cap='49', s='write a string...'
** read 5 bytes...
buff cap='44', s=' a string...'

[Ian Lance Taylor]

ziyu_huang <ziyu4...@gmail.com> writes:

> I wonder where will be the way to Go in "enhance string operation"
> performance.
> In Go the string seems just work, there is not much performance fine
> tune. So, if you do some string operation, you will see it's much
> slower compare to Java or Python.
>
> So, will Go enhance string ? Or Go will adopt another approach for
> enhance string operation ?

Can you give some examples of what kind of enhancements you mean?

Ian

[ziyu_huang]

Hi Ian,

The problem I encounter is the performance about sprintf. The sprintf
in C is MUCH faster then Go one.

for example, 1000000 loop at simple sprintf
char key[100];
char val [100];
for() {
sprintf(str, "%d", i);
sprintf(st, "key%d", i);
}

in Go.

for i:=0; i < 1000000; I++{
key:=fmt.Sprintf("%d", i)
val:=fmt.Sprintf("key%d", i);
}

I don't know the performance is because the fmt or something else. So,
I try to use bytes.Buffer, it's faster, but still poor compare C
version.
key:=bytes.NewBuffer(...)
val := bytes.NewBuffer(...)
for i:=0; i < 1000000; I++{
key.Reset(); val.Reset();
key.WriteString(strconv.Atoi(i));
val.WriteString("key");
val.Write(key.Bytes());
}

By the "enhance" I mean two things.

1. Some String operation looks bad performance compare to other
language, I there any plan to improve it ? Or you will suggest to use
some other better approach.
2. I don't find anything like Java's StringBuffer, the most equivalent
is the bytes.Buffer() . But it lacks a lot of function compare to
Java's or Python's.
Is there any plan to provide equivalent one and more syntax sugar on
it more then just plain structure.

String operation is quite important to the performance of server side
web application, and also database.

On 12月2日, 上午7時31分, Ian Lance Taylor <i...@google.com> wrote:

[Russ Cox]

On Tue, Dec 1, 2009 at 17:31, ziyu_huang <ziyu4...@gmail.com> wrote:
> Hi Ian,
>
> The problem I encounter is the performance about sprintf. The sprintf
> in C is MUCH faster then Go one.

That's because this has no memory allocations in it:

> for example, 1000000 loop at simple sprintf
> char key[100];
> char val [100];
> for()  {
> sprintf(str, "%d", i);
> sprintf(st, "key%d", i);
> }

and this has 2 million allocations:

> for  i:=0; i < 1000000; I++{
>    key:=fmt.Sprintf("%d", i)
>    val:=fmt.Sprintf("key%d", i);
> }

It has little to do with the speed of string operations.

[Brian Slesinsky]

I think if you use fmt.Fprintf() with a bytes.Buffer as its first
argument, that's a closer equivalent to sprintf() in C. How does that
do?

- Bran

[ziyu_huang]

fmt.Fprintf(bytes.Buffer, "%d", i) is MUCH MUCH poor performance then
bytes.Buffer.WriteString(strconv.Atoi()).

Using bytes.Buffer(). is close to C's sprintf() , but still 2 or 3
times slower order.

[ziyu_huang]

I can't agree you more. String manipulations is critical in server-
side web application.
That's why Java/Python/Ruby spend so much effort on optimize its
performance.
If Go doesn't target on this area, I don't know what Go can target,
replace C ?

On 12月2日, 上午10時48分, inspector_jouve <kaushan...@gmail.com> wrote:
> >and this has 2 million allocations
>

> It has much more than 2 million allocations (string or otherwise), and
> that's exactly the problem.
> The point is: most applications these days are doing nothing but
> string manipulations: take data from one place, decode it, encode it,
> send to another places, encode it, send to log, marshal - unmarshal,
> serialize- deserialize, etc.. No algorithms, no computations, just
> string manipulations. This is typical picture. If string manipulations
> are slow, many people will decide that the language is not suited for
> these kinds of tasks - but there's no inherent reasons in the language
> for such conclusion. It's just because particular implementation of
> string methods is a bit slow. IMHO, go should perform in this area at
> least on par with java. I'm not sure how to achieve this, though.

[Jessta]

Seriously guys, all these micro-bench marks are kind of silly.

At this stage the language is more important than the implementation
of the language, we've got years to tweak the implementation.
The garbage collector is being re-implemented, the runtime hasn't been
optimised and none of the libraries have been optimised either because
there is no point trying to optimise anything until the language
syntax is stable and the new garbage collector is in so we can see the
actual bottlenecks.

If you're using this language in production right now then you're
probably crazy, if you're not using it in production then the
performance isn't really important.

What is needed right now is for people to write code in Go and learn
the syntax and the Go way of doing things, for people to write library
code so that when the optimisations finally do come along the language
has a really powerful and useful standard library.

- jessta
--
=====================
http://jessta.id.au

[hong]

Hi, Huang et al,

If you have bandwidth, I recommend you implement an in-memory
stream struct. It will have the following capabilities.

* it uses []byte for storage, so you can get the underlying buffer
and use it anywhere you like.

* it supports all standard string operations.

* it can be cleared and reused as many times as you like.

* it supports in-place Printf(), so it will perform closely to C
sprintf().

* it supports in-place Scanf(), equivalent to sscanf()/fscanf().

* it supports in-place Pack()/Unpack(), equivalent to Perl pack/
unpack.

* it supports standard File operations, Read/Write/Close.

* it supports in-memory pipe (read head write tail).

* it can take mmap region as []byte, and process entire file
without using read/write system calls.

* if a file descriptor is associated with the stream, this stream
automatically becomes buffered file stream. By replacing the
fd on the file, it supports chunked files.

It sounds like a kitchen sink object. In practice, it is just enhanced
version of C FILE*. I found it extremely useful. I implemented
such thing once, and it needs about 5000 LOC in C. I will be
happy to implement such a library for Go, but I am unlikely
to have time this month.

Hong

[Dimiter "malkia" Stanev]

Well said.

[ziyu_huang]

Don't you see I mention there is something missing like Java's
StringBuffer?

I know what's the performance is going on, so I am discussing what Go
should address. I know allocation will be address after GC is done.
But the GC is not only issues, if you look my post examples. If you
use fmt.Fprintf() on bytes.Buffer() thee performance is still poor. I
wonder
there is something wrong in the deep.(perhaps reflection ?)

So, I am not talks about performance of string manipulation ONLY. I
think Go should have good string manipulate framework just like Python
have.
So where is mutable string? will there be one ? this is basic thing
that a modern language should provide.

[baldmountain]

On Dec 2, 1:32 am, Jessta <jes...@gmail.com> wrote:
> Seriously guys, all these micro-bench marks are kind of silly.
>

+1

> What is needed right now is for people to write code in Go and learn
> the syntax and the Go way of doing things, for people to write library
> code so that when the optimisations finally do come along the language
> has a really powerful and useful standard library.
>

+1

[roger peppe]

2009/12/2 ziyu_huang <ziyu4...@gmail.com>:

> there is something wrong in the deep.(perhaps reflection ?)

yes, i think the reflection in the Printf family does
slow it down quite a bit. try doing the string conversions
directly and see how much that speeds it up.

[Ben Tilly]

On Wed, Dec 2, 2009 at 3:04 AM, ziyu_huang <ziyu4...@gmail.com> wrote:
> Don't you see I mention there is something missing like Java's
> StringBuffer?

[...]

> So where is mutable string? will there be one ? this is basic thing
> that a modern language should provide.

[...]

This is important.

The use case here is incrementally building up a large string. For
instance you are building up an HTML table from a database table. The
code isn't complicated, but there is a lot of

myHtml += anotherPiece;

going on.

With immutable strings as Go has, every time you do this you recopy
the string. This is a O(n*n) algorithm. There are several possible
improvements over this naive strategy.

1. Mutable strings. When you create a string, allocate a fixed
fraction more space than is needed. Then when appending you only have
to reallocate if you're going to run out of buffer. Building a long
string this way is O(n). Perl uses this strategy for all strings.

2. Have a special data type for lots of pieces of string that will be
joined later. There are several ways of doing it under the hood that
are O(n). This is what Java's StringBuffer does.

3. Create a vector of strings. Push on more strings as they come.
Join them at the end. This is theoretically O(n) but building a long
string this way provides an interesting stress test for the garbage
collector that can do bad things. I've used this strategy in
JavaScript.

4. Do the same as 3 except with a multi-level join strategy. For
instance in building a table, you could incrementally add each field
in the table, join each row once it is complete, then join the rows
once the table is complete. I've been forced to this strategy in
JavaScript when the previous one performed badly. (This was some
years ago, modern browsers likely do better now.)

I think that it is imperative in the long run for Go to make at least
one of #1, #2 or #3 perform well. To the extent that there is a
currently a plan, it is likely to make #3 work well. However I
believe that #1 and #2 both can offer better performance and memory
characteristics.

Cheers,
Ben

[roger peppe]

2009/12/2 Ben Tilly <bti...@gmail.com>:

> With immutable strings as Go has, every time you do this you recopy
> the string.  This is a O(n*n) algorithm.

i'd guess that if the string is in a local variable and the compiler
can tell that it's not aliased, then it could potentially optimise
away the copying
and just add to an in-place buffer.

[atomly]

On Tue, Dec 1, 2009 at 9:48 PM, inspector_jouve <kaush...@gmail.com> wrote:
>>and this has 2 million allocations

> It has much more than 2 million allocations (string or otherwise), and
> that's exactly the problem.

I think you're missing Russ's point. The Go code has :=, meaning
allocate and assign, inside the for loop, whereas the C code declares
the variables outside of the for loop.

--
:: atomly ::

[ ato...@atomly.com : www.atomly.com : http://blog.atomly.com/ ...
[ atomiq records : new york city : +1.917.442.9450 ...
[ e-mail atomly-new...@atomly.com for atomly info and updates ...

[Ian Lance Taylor]

I don't see any particular problem with writing Go code which
implements any of your options. But it does mean using a data
structure which is not named "string".

Immutable strings are nice because they are fast to copy. Since Go
passes strings by value, they are frequently copied. So I think it
makes all kinds of sense to make them immutable.

But it does mean that the += string concatenation operator is a bit of
an attractive nuisance, since it looks efficient but really isn't. So
I think the tradeoff here is between the convenience of +, which
implies +=, and the perhaps surprising efficiency cost of using those
operators.

Ian

[Ben Tilly]

Given that the need is common, I would suggest having one of those
alternate solutions in core.

> Immutable strings are nice because they are fast to copy.  Since Go
> passes strings by value, they are frequently copied.  So I think it
> makes all kinds of sense to make them immutable.
>
> But it does mean that the += string concatenation operator is a bit of
> an attractive nuisance, since it looks efficient but really isn't.  So
> I think the tradeoff here is between the convenience of +, which
> implies +=, and the perhaps surprising efficiency cost of using those
> operators.

One somewhat annoying solution could be to have the core implement two
string types. Don't allow "string" to use +=, but do allow
"mutableString" to use it. The official rationale behind the
restriction could be that it makes no sense to mutate an immutable
thing. The real reason would be exactly to push people towards the
efficient version of what they are trying to do.

Cheers,
Ben

[Bovlb]

> There are several possible improvements over this naive strategy.
>

> 1. Mutable strings.  [...] Perl uses this strategy for all strings.

>
> 2. Have a special data type for lots of pieces of string that will be

> joined later.  [...] This is what Java's StringBuffer does.
>
> 3. Create a vector of strings.  [...] I've used this strategy in

> JavaScript.
>
> 4. Do the same as 3 except with a multi-level join strategy.

In C++, the typical approach to this problem would be to write to a
stream, typically an ostringstream that is later converted back into a
regular string using str().

It's tempting to try to reproduce this in Go using channels. For
example, you could have a go-routine than inputs strings from one
channel, and emits a single string to another when the first channel
is closed. Internally it constructs the string as efficiently as it
can. If you're planning to send this HTML across a socket, then maybe
you can skip the string part altogether and just copy the bytes to the
socket's channel. Both would have the same interface from the
writer's perspective.

[Mike Zraly]

Why use channels for this?  Why not have a class with an Append method?
Or are you using channels to serialize delivery and avoid concurrent mutation
of the string being constructed?  If so wouldn't a simple mutex be simpler,
even if it does go against the mantra of communicating to synchronize instead
of synchronizing to communicate?

I think this brings up a very important point -- in a language designed to run
in multiple threads with shared address space, immutability is a win for safety.
If you want a thread-safe mutable string you have to pay with some sort of
synchronization to guard against concurrent mutation.  You then discover
that synchronization isn't free and decide you need an unsafe mutable string.
Java already went down this path with StringBuffer and StringBuilder.
Maybe that's the right model, maybe not.  But the point is that it's really
not as trivial an exercise as some people seem to think.

[Jessta]

On 03/12/2009, Bovlb <goo...@meninx.com> wrote:
> In C++, the typical approach to this problem would be to write to a
> stream, typically an ostringstream that is later converted back into a
> regular string using str().
>

You might want to look at the bytes package and the buffer type.



--
=====================
http://jessta.id.au

[Brian Slesinsky]

On Dec 2, 6:00 am, inspector_jouve <kaushan...@gmail.com> wrote:
> >The garbage collector is being re-implemented
>

> Garbage collector has nothing to do with the problem.
> Even ideal garbage collector cannot reduce the number of allocations.

Although I don't remember most of what I read about how Java's garbage
collector works, I believe the allocation itself is something very
cheap like adding a constant to a pointer.

- Brian

[Bob Cunningham]

On 12/02/2009 09:53 PM, inspector_jouve wrote:
> As a side note, I wonder how Printf found its way into modern
> programming language at all. It's ancient, came from Fortran, where it
> was good for printing endless rolls of formatted tables filled with
> numbers for rocket scientists.
> But these days are gone. I don't remember last time when I saw a table
> that was not an HTML table (probably at the same time when I saw
> IBM-360 in action).
> But maybe I'm wrong, and this is still a good idea?
> Then, how about this: suppose instead of x=a*b+c, we will write
> x=math.Eval("+*",a,b,c).
>
> How is that not a good idea then? I can argue that this notation is
> actually a great invention: it allows you to easily add operators,
> define operations on exotic types (e.g., matrices, tensors, what-not),
> etc.
> But Printf *essentially* uses the same notation, we just don't call it
> Polish, but that's what it is: operators in one place, operands in
> another... Where is the difference?

That's *completely* the wrong perspective! (IMHO, of course.)

It is much more useful to think of printf as a domain-specific embedded mini-language optimized for simple formatted output presentation. That's all, nothing more. It is the smallest useful thing that keeps you away from full markup/formatting/presentation languages (nroff/troff, TeX, HTML/CSS, XML, etc.).

The algebraic notation (both numeric and logical) used in programming languages is another mini-language, optimized for expressions. It also happens to be close to the mathematical notation we learned in school, which is a good thing, but one that can be carried to an extreme (consider APL).

The language of functions permits procedural and functional programming to interface to algebraic expressions. Go's goroutines fit in here too.

I think of Go's channel notation as another mini-language, optimized to simplify IPC.

Declarations (and the type/object system) are yet another mini-language, where Go tidies up C/C++ confusion and difficulty.

How all these mini-languages fit together is what distinguishes a "clean" language from a messy, cluttered, confusing, or awkward one. Not only must each mini-language be good by itself, but when unified into a single programming language, they all must mix as seamlessly and as easily as possible, so as not to make any particular programming paradigm needlessly difficult or awkward to implement in the language.

Go, being a very young language, is still evolving in this area. In some ways it may seem clunky, but being small, powerful, and expressive goes a long way toward making up for that.

And as for printf, well, I can't think of anything less that would be as useful (FWIW, I believe C++ fails badly in this respect). If you need more, Go does have other packages available, or you could write your own.


-BobC

[Rowan Davies]

I've used char iterators for such things in C# and F#, and I can say
that it does tend to allow you nicely separate concerns, and often
with no noticable effect on performance. Channels should be similar -
and I think it's a style worth considering - I'd think of it as an
opportunity do things in a better way rather than compensating for
anything.

Note that concatention of strings like this is known to be a thorny
issue for performance with strictly linear representations. See,
e.g.:

http://blogs.msdn.com/jscript/archive/2008/03/19/insight-into-string-concatenation-in-jscript.aspx

It's surprising how many programmers aren't aware of these issues and
happily concatenate everywhere, assuming that it's a fast operation.

Using string buffers is the standard solution. Ropes are more
sophisticated immutable string data structure that frees programmers
from worrying about buffers by mixing linear and tree representations
- and for some purposes would be nice to have them handy to supplement
the standard strings - but I don't think Go requires them urgently.

- Rowan


On Dec 3, 11:36 am, inspector_jouve <kaushan...@gmail.com> wrote:
> If people need to use channels to compensate for the lack of mundane
> string operations, this indicates a major problem.

[Ian Lance Taylor]

inspector_jouve <kaush...@gmail.com> writes:

> Hmm... "Optimized"? Well, in what sense it's optimized? The whole
> story is about poor performance of this "optimized" apparatus, which
> works through reflection. What about type safety? Format may require
> int, and you pass Foobar instead?
> I wonder - language is so pedantic with regard to type safety
> everywhere (this is a Good Thing. don't take me wrong), but at the
> same time welcomes this ad-hoc mini-language with no type control at
> all.

The printf mini-language is type controlled in Go. There is no crash
or type violation when using %d to print a string, for example.

It is certainly more efficient to use precise convertors, such as
strconv.Itoa, than it is to use Printf. But there are times when
Printf is quite convenient. I agree that it should be made more
efficient.

Ian

[SnakE]

2009/12/3 inspector_jouve <kaush...@gmail.com>

As a side note, I wonder how Printf found its way into modern
programming language at all. It's ancient, came from Fortran, where it
was good for printing endless rolls of formatted tables filled with
numbers for rocket scientists.
But these days are gone. I don't remember last time when I saw a table
that was not an HTML table (probably at the same time when I saw
IBM-360 in action).

Printf and friends significantly reduce awkward typing.  It's possible to write in C#:

x = "Some thing: " + thing + ", another: " + other + " and third " + foo + ".";

But everybody switches to string.Format() as soon as the number of pluses exceeds three.  Because

x = string.Format("Some thing: {0}, another: {1} and third {2}.", thing, other, foo);

while being a bit longer, makes it absolutely clear what the formatted string will look like.  And you need to type much less plus-space-quote-comma in different combinations which is a sort of tongue twister for fingers.

[Rowan Davies]

No, no. You can statically catch errors like the wrong type or number
of arguments to printf. OCaml has been doing that for years, in a
fundamentally sound way, with printf in a library.

Read about it, and you'll see. I'm amazed people are so quick to
assume they are an expert and state facts about languages when they
have a clear lack of exposure to such advanced language concepts.
Personally, I am still learning.

- Rowan



On Dec 4, 12:48 am, inspector_jouve <kaushan...@gmail.com> wrote:

> That's exactly my point!
> Passing string where int is expected is obviously a bug. This bug
> cannot be caught by compiler - turns out, it will not be caught by
> runtime either? I can easily come up with example where one thing will
> lead to another, and in the end your rocket will land on Venus instead
> of Mars, just because language generously accepted anything in place
> of anything else here. Bypassing type safety control here is *unsafe*,
> according to terminology of go, and like all unsafe operations, should
> be used "under restricted conditions" (you remember I asked what this
> means?)

[Rowan Davies]

To be clear: yes Go doesn't seem to be doing such checking. But,
certainly it has been done in other statically typed languages.

It's a nice suggestion that Go do that checking too. I doubt it's the
highest priority, but certainly there's no technical reason why it
can't be done as long as the format string is a constant, so likely it
will happen in time.

Maybe you could implement yourself if it worries you? This is an open
source project after all.

[Jessta]

On 04/12/2009, Rowan Davies <rd1...@gmail.com> wrote:
> No, no. You can statically catch errors like the wrong type or number
> of arguments to printf. OCaml has been doing that for years, in a
> fundamentally sound way, with printf in a library.

...only if the format string is static

--
=====================
http://jessta.id.au

[Rowan Davies]

Yep. But, most other useful cases can be rephrased with static
formats. The rest are rare enough that using + is unlikely to injure
your fingers.

- Rowan

[Ian Lance Taylor]

inspector_jouve <kaush...@gmail.com> writes:

> Guys, what if I just go ahead and open an issue for supporting this:
> x:="Some thing:{thing},another:{other} and third {foo}"

I don't think it is particularly desirable to tie string formatting
that tightly into the language proper.

How do you feel about

x := fmt.Sprint("Some Thing:", thing, "another:", other, " and third ", foo);

?

Ian

[SnakE]

2009/12/3 inspector_jouve <kaush...@gmail.com>

Guys, what if I just go ahead and open an issue for supporting this:

x:="Some thing:{thing},another:{other} and third {foo}"

where all these {things} are expressions, e.g
"Some thing:{i+j} another:{getDate()} and third {myVar}"
Is there a precedent in any other language?
Isn't it convenient?.

I don't know.  It's too novel.  Basically you propose to make { a syntax sugar for "+ and } for +" so that things are not actually parts of the string.  Should the following work?

"Some thing: { foo("a", "b") }"

If special formatting is required, it can be passed like this:
"Some thing {i+j:5d} " - that is, separated by colon or something (but
it's really rarely needed - may be an unnecessary feature - I'm not
sure).

How do you format a hexa-decimal number?  How do you format time so that minutes occupy exactly two decimal places, with zero filling?

Then it will work really fast!

I fail to see how this sugary sugar will speed up the actual formatting.

[ziyu_huang]

I think without compiler's help the reflection will just kill the
performance.
I think Go should provide more function and performance enhance for
constructor string for mutable-string.
Of cause you can always write your own, but it will be hard to
communicate with other's codes.

Can we have a StringBuffer in Go ? bytes.Buffer seems not good enough.
And I do hope Go can provide more better syntax-sugar and performance
that only compiler can do.

On 12月4日, 上午3時02分, Ian Lance Taylor <i...@google.com> wrote: