release.2010-11-10
Rob 'Commander' Pike
We've just tagged a new Go release, release.2010-11-10. As usual, you can update by running:
hg pull
hg update release
The birthday release includes a new Search capability inside the sort package.
It takes an unusual but very general and easy-to-use approach to searching
arbitrary indexable sorted data. See the documentation for details:
http://golang.org/pkg/sort/#Search
The ARM port now uses the hardware floating point unit (VFP). It still has a
few bugs, mostly around conversions between unsigned integer and floating-point
values, but it's stabilizing.
In addition, there have been many smaller fixes and updates:
* 6l: generate dwarf variable names with disambiguating suffix.
* container/list: make Remove return Value of removed element.
makes it easier to remove first or last item.
* crypto: add cast5 (default PGP cipher),
switch block cipher methods to be destination first.
* crypto/tls: use pool building for certificate checking
* go/ast: change embedded token.Position fields to named fields
(preparation for a different position representation)
* net: provide public access to file descriptors (thanks Keith Rarick)
* os: add Expand function to evaluate environment variables.
* path: add Glob (thanks Benny Siegert)
* runtime: memequal optimization (thanks Graham Miller)
prefix all external symbols with "runtime·" to avoid
conflicts linking with external C libraries.
My apologies if I have missed anyone's contributions in the above list.
We appreciate all the help.
To see all changes from the last release to this one, you can,
after updating, run
hg log -r release.2010-11-02:release.2010-11-10
Have at it!
Rob
MC.Spring
Mark Summerfield
> The birthday release includes a new Search capability inside the sort
> package. It takes an unusual but very general and easy-to-use
> approach to searching arbitrary indexable sorted data. See the
> documentation for details: http://golang.org/pkg/sort/#Search
I'm curious why sort.Search() doesn't return -1 if the item isn't found.
That would mean:
elem := 23
i := sort.Search(len(data), func(i int) bool { return data[i] <= elem })
if i != -1 {
// elem is present at data[i]
} else {
// elem is not present in data
}
Which is consistent with, say, strings.Index().
--
Mark Summerfield, Qtrac Ltd, www.qtrac.eu
C++, Python, Qt, PyQt - training and consultancy
"Advanced Qt Programming" - ISBN 0321635906
http://www.qtrac.eu/aqpbook.html
nsf
Mark Summerfield <ma...@qtrac.eu> wrote:
> On Wed, 10 Nov 2010 15:21:54 -0800
> "Rob 'Commander' Pike" <r...@google.com> wrote:
> > It's Go's first anniversary. To celebrate:
> [snip]
> > The birthday release includes a new Search capability inside the sort
> > package. It takes an unusual but very general and easy-to-use
> > approach to searching arbitrary indexable sorted data. See the
> > documentation for details: http://golang.org/pkg/sort/#Search
> [snip]
>
> I'm curious why sort.Search() doesn't return -1 if the item isn't found.
> That would mean:
>
> elem := 23
> i := sort.Search(len(data), func(i int) bool { return data[i] <= elem })
> if i != -1 {
> // elem is present at data[i]
> } else {
> // elem is not present in data
> }
>
> Which is consistent with, say, strings.Index().
Because it doesn't check for equality. It just looks for potential
position and then you should do the equality test.
Mark Summerfield
Ooops, sorry, I was thinking of < rather than <=.
roger peppe
> I'm curious why sort.Search() doesn't return -1 if the item isn't found.
what nsf says is true, but, also i *thought* that the idea is that the result
also tells you where to insert a new item if it's not already there,
but i hadn't
looked at the spec too closely.
<bikeshed>
IMHO the current design makes it fairly awkward to use
Search for inserting new elements, as searching in
an empty array returns 0, but searching in a one element
array also returns 0, although the new element might end
up at index 0 or 1.
here's insert as implemented for the current Search
(simpler versions welcome, please!)
func insert(a []int, x int) []int {
if len(a) == 0 {
return append(a, x)
}
i := sort.Search(len(a), func(j int) bool {
return a[j] <= x
})
if a[i] == x {
return a
}
if a[i] > x {
i--
}
a = append(a, 0)
copy(a[i+2:], a[i+1:])
a[i+1] = x
return a
}
if Search was changed so that it returns n if x > all elements in the
array, then insert becomes quite a bit simpler:
func insert(a []int, x int) []int {
i := sort.Search(len(a), func(j int) bool {
return a[j] <= x
})
if i >= len(a) {
return append(a, x)
}
if a[i] != x {
a = append(a, 0)
copy(a[i+1:], a[i:])
a[i] = x
}
return a
}
and the test for equality after the search is no harder (if the array
might be empty,
you have to test for i >= len(a) anyway).
</bikeshed>
Robert Griesemer
roger peppe
> Append might become simpler, but Search is likely to become more expensive
> for all uses, not just Append. Search calls f log2(n) times; it's hard to
> improve on that, and easy to make it significantly worse with one extra call
> (for n = 1024, going from 10 to 11 calls results in a 10% slowdown).
surely that's only true if the function is expensive to call.
i'd have thought that the cost of the closure allocation would
usually dwarf the cost of the extra function call.
> I am happy to be convinced otherwise, ideally with a CL.
CL submitted.
> The original design is by E.W.Dijkstra and even requires that the array to
> be searched is not empty. Luckily, a simple change avoids a crash in this
> case in our code. However, in most situations one will have to check the
> empty case; and it often doesn't make sense to call Search in that case in
> the first place (it's more efficient not to, too).
the CL does not change this.
> If there is a common use case that would benefit from a Search that gives
> more precise information, I would suggest a wrapper function instead of
> compromising the elegance and performance of Search. In fact, if that makes
> the logic of Append simpler to understand, you could just write the wrapper
> locally.
i contend that the revised semantics are almost always easier
to comprehend and use.
- it deals neatly with the case that there are multiple matches (slicing
from i to the end of the array gives you an array starting with all the
occurrences of x)
- inserting a new element becomes trivial, as per my above post.
- the functional description is considerably shorter, and has no special cases.
it's not possible to write a wrapper function around the current search
to give you these semantics and still keep O(log2(n)) performance
(you'd have to linearly scan back from the matched item).
if you really think that the performance hit from calling f one
more time is crucial, then that's fine - i'll abandon the CL.
Russ Cox
not backward-compatible and will not be caught
during a recompile (the type didn't change):
> * crypto: ...
> switch block cipher methods to be destination first.
That is, if you call Decrypt(src, dst) or Encrypt(src, dst),
you need to change it to Decrypt(dst, src) or Encrypt(dst, src).
The change here is a little painful but brings them in line
with all other Go functions that operate on a source and
destination []byte. It is also rare for these functions to be
invoked directly; using the reader and writer interfaces
provided by the various mode wrappers is much more common,
and those don't need to change.
But if you see mysterious breakage in code doing low-level
crypto, you might look here first.
Russ