Strongly Typed Binary Search Tree without using casts, interface{}, or reflection

[Nate Finch]

I wrote this mostly as a proof of concept, so don't expect it to tie your shoes for you :)

https://github.com/natefinch/tree  is the base library,

https://github.com/natefinch/treesample is a runnable example.

The basic idea is to separate data storage from data organization. A slice (or other index-able data structure) holds the data, the tree organizes it, using the indices as references to the values.

To create a tree of a new type, all you have to do is define a Compare function for your datatype (returning -1, 0, or 1). Then you can construct a tree from a slice of that data, using the compare function to tell the tree where to put the items.

The actual tree struct is just

type Tree struct {

    Val int

    Right *Tree

    Left *Tree

}

Where Val is the index of the item in your data structure.

Mostly I wanted to prove to myself that this was possible in Go, and without too much hassle from the programmer. It's not zero work to implement a new tree, but there's very little actual work. With a proper red/black or AVL tree, you'd be saving yourself a lot of rewriting/copy & paste of the algorithms.

Obviously a Remove method would be useful (and would be somewhat non-trivial, which is why I skipped it for now ;)

Let me know what you think, and if there's a better way to do anything in here.

[John Asmuth]

This is pretty neat.

Instead of a passed function, why not use, eg, sort.Interface?

[Nate Finch]

I was using a closure to include the value you're looking for, to get around needing to specify a type in the signature of the function, and to avoid having to put anything you looked for into the backing datastructure.

Using sort's Less would work for the insert case, but for searching, you might not want to have to add the value to your data structure in order to look for it.  Also, Less can't return "equals", which is needed for searching (otherwise you'd have to do a second compare of the value, since it might return a value slightly greater than your value, rather than the exact value.

If the API of tree can be improved to use something more similar to sort.Interface, that would be great.

[David DENG]

Why you have to store all entries in a slice. The Remove action will be compilcated.

I suggest the Tree.Val can be an interface{}, and a static customized comparison function with two interface{} is needed.

type Tree struct {

    cmp func(interface{}, interface{}) int

    root *Node

}

type Node struct {

    val interface{}

    left, right *Tree

}

Another suggestion is that the Walk function need not return the Tree data-structure, instead just returns the value only.

David

[Nate Finch]

The whole point is to be strongly typed, and avoid casting, which is why I didn't use interface{}. Using interface{} is trivial and not interesting. :) Yes, remove is complicated, but not impossible.

The reason walk returns the tree instead of the value is that you can then operate on the Tree it returns, if you want.

Actually, I should have search return the Tree, too, so you can easily peel off a subsection of the tree (note there's an unexported search method that does just that, which I was going to use for Remove as well).

[John Asmuth]

Remove isn't really that bad - if you use sort.Interface (or something similar with methods relevant here), you can do a compacting remove with two operations: s.Swap(i, s.Len()-1), s.RemoveLastElement().

On Monday, February 25, 2013 2:03:55 PM UTC-5, David DENG wrote:

[David DENG]

Casting from and to an interface{} is cheap. You can do with an wrapper type.

I don't think you can easily do removing in the current data-structure. The point is, when you store elements in a search tree, they need to be maintained in a linear way as well.

David

[Ethan Burns]

On Monday, February 25, 2013 2:32:47 PM UTC-5, John Asmuth wrote:

Remove isn't really that bad - if you use sort.Interface (or something similar with methods relevant here), you can do a compacting remove with two operations: s.Swap(i, s.Len()-1), s.RemoveLastElement().

You then have to find the last element's node in the tree to update its index.

Ethan

[Kyle Lemons]

Boxing/unboxing an interface{} is not as cheap as a slice index.

--
You received this message because you are subscribed to the Google Groups "golang-nuts" group.
To unsubscribe from this group and stop receiving emails from it, send an email to golang-nuts...@googlegroups.com.
For more options, visit https://groups.google.com/groups/opt_out.
 
 

[Dan Kortschak]

In this situation for biogo.llrb, I used a Comparable interface that returns an int, negative for less, zero for equal and positive greater. The code overhead to wrap types to do alternative queries is not huge.

[Ethan Burns]

I wonder if you could do the remapping lazily by keeping an extra array to track, for each index, where it has moved.

Ethan

[David DENG]

Sorry: The point is, when you store elements in a search tree, they need NOT be maintained in a linear way as well.

David

[Jan Mercl]

On Mon, Feb 25, 2013 at 8:52 PM, Ethan Burns <burns...@gmail.com> wrote:
>> You then have to find the last element's node in the tree to update its
>> index.
>
>
> I wonder if you could do the remapping lazily by keeping an extra array to
> track, for each index, where it has moved.

I'm doing something a bit similar for a BTree, and after struggling
with this kind of troubles I moved the "backend" to a cca
`map[int]thing` instead of a slice
(https://github.com/cznic/tmp/blob/master/lldb/btree.go#L256). The
difference is that there the "thing" is always a []byte, but the
problem is the same.

-j

[John Nagle]

On 2/25/2013 11:35 AM, David DENG wrote:
> I don't think you can easily do removing in the current data-structure. The
> point is, when you store elements in a search tree, they need to be
> maintained in a linear way as well.

Just think of it as an index to data stored elsewhere.
You can have multiple indices based on different comparison
functions, like databases do.

John Nagle

[Nate Finch]

Note that there's not actually two copies of the data. The tree only holds the index.  Think of the index as a pointer to the actual value.

Jan: about using a map - I thought of that too, but you still need to compact the keyspace... i.e. if you remove index "7" from the map, you need to be able to figure out that "7" is a usable key again. I guess if you use a uint64 as your key, you have a long time before you run out of keys just by incrementing the last used index on insert.

[Jan Mercl]

On Mon, Feb 25, 2013 at 9:40 PM, Nate Finch <nate....@gmail.com> wrote:
> Note that there's not actually two copies of the data. The tree only holds
> the index. Think of the index as a pointer to the actual value.
>
> Jan: about using a map - I thought of that too, but you still need to
> compact the keyspace... i.e. if you remove index "7" from the map, you need
> to be able to figure out that "7" is a usable key again. I guess if you use
> a uint64 as your key, you have a long time before you run out of keys just
> by incrementing the last used index on insert.

int64 is used actually b/c of some other reasons, but let me do a
quick check: Assign a new handle once per 10 nanoseconds -> running
out of them in 2^63 * 10^-8s, which is about 2923 years B-)

-j

[Nate Finch]

On Monday, February 25, 2013 3:47:06 PM UTC-5, Jan Mercl wrote:

quick check: Assign a new handle once per 10 nanoseconds -> running 
out of them in 2^63 * 10^-8s, which is about 2923 years B-) 

That's a good point :) 

It does use an extra 8 bytes per item, though (+4 in the Tree and +4 in the map).

Not having to do any extra cleanup on delete is awfully nice though.

[Ethan Burns]

On Monday, February 25, 2013 3:40:55 PM UTC-5, Nate Finch wrote:

Note that there's not actually two copies of the data. The tree only holds the index.  Think of the index as a pointer to the actual value.

Jan: about using a map - I thought of that too, but you still need to compact the keyspace... i.e. if you remove index "7" from the map, you need to be able to figure out that "7" is a usable key again. I guess if you use a uint64 as your key, you have a long time before you run out of keys just by incrementing the last used index on insert.

Can't you use John's suggestion of swapping the last index into the "empty spot" now made free by the removal of 7?  The only difficulty is that you have to find the node corresponding to the element moved into the 7 slot.  This can be done with the auxiliary slice mapping indices to tree node pointers (a slight improvement on my suggestion above):

func (tree *Tree) Remove(i int) {

     normal binary tree removal of node for node with value i

     // Plug hole in the array by swapping the last element into it.

     s.Swap(i, s.Len()-1)

     s.RemoveLastElement()

     // Update the last element's .Val field to correspond to its new index: i

     // nodeByIndex is a slice where each element is a pointer to the node with .Val corresponding to the index.

     // E.g., nodeByIndex[5] is a pointer to the tree node with Val=5 (or nil if there isn't one).

     // This slice should be easy to keep up-to-date on insertions too.

     movedNode := tree.nodeByIndex[s.Len()]

     tree.nodeByIndex = tree.nodeByIndex[:s.Len()+1] // nodeByIndex should always be of size s.Len()
     tree.nodeByIndex[i] = movedNode
     movedNode.Val = i

}

Maybe there's a bug in there (it's a bit of a mess), but hopefully it demonstrates the idea well enough.

Ethan

[Nate Finch]

On Monday, February 25, 2013 4:03:06 PM UTC-5, Ethan Burns wrote:

Can't you use John's suggestion of swapping the last index into the "empty spot" now made free by the removal of 7?  The only difficulty is that you have to find the node corresponding to the element moved into the 7 slot.  This can be done with the auxiliary slice mapping indices to tree node pointers (a slight improvement on my suggestion above):

Yeah, my original thought was to do the swapping compaction on the slice... however, I hesitate to introduce a third datastructure that needs to be kept in sync.  In theory you can just do another O(logN) search of the Tree to find the node that corresponds to the item at the end of your slice.  That seems like it would be a better tradeoff than maintaining a whole extra list of reverse pointers.

Not sure whether that would be better or worse than Jan's suggestion to just throw away int64 keys on delete.

Man, computer science really is all about tradeoffs.  :)

[Nate Finch]

Also, this is exactly why I posted before writing Remove :)  I figured someone on this list would have an opinion ;)

[mau...@murus.org]

Dear Nate Finch,

I do not know, if these ideas may help you,
but you might have a look into my ideas:
http://murus.org/go/ - get murus.tgz and look
into my package "murus/set".

Greetings,
Christian

[David DENG]

interface{} is the perfect 'map' you could get trivially. The key is the physical address of the data generated alone with the data, and can be used to reach out the data(value) both efficiently and in a thread-safe way. The only overhead is the type information which is much cheaper than the map lookup or tree-search for removing. And the program accordingly is the more straightforward.

Give a reason me a reason not using it.

David

[David DENG]

Just putting the data or its pointer, as an interface{}, to different binary tree.

David

[Jan Mercl]

On Mon, Feb 25, 2013 at 10:37 PM, David DENG <david...@gmail.com> wrote:
> interface{} is the perfect 'map' you could get trivially. The key is the
> physical address of the data generated alone with the data, and can be used
> to reach out the data(value) both efficiently and in a thread-safe way. The
> only overhead is the type information which is much cheaper than the map
> lookup or tree-search for removing. And the program accordingly is the more
> straightforward.
>
> Give a reason me a reason not using it.

The reason is that in Nate's design of a binary tree you can have the
back-end storage strongly typed and you do not need interface{} at
all. Additionally interface{}:

- make access slower (even if a little).
- requires type assertions to use.

IOW, if working specifically with e.g. int elements, []int is always
better than []interface{}. The later is good for a slice of not only
one specific type.

-j

[John Asmuth]

On Monday, February 25, 2013 4:37:48 PM UTC-5, David DENG wrote:

Give a reason me a reason not using it.

I don't think anyone is saying you shouldn't use it. Feel free - I like https://github.com/petar/GoLLRB myself.

One question worth answering is this: how long does it take to assert the base type out of the interface, vs indexing into an array to get the data?

I suspect that they both take the exact same time.

[John Asmuth]

On Monday, February 25, 2013 4:43:09 PM UTC-5, Jan Mercl wrote:

- make access slower (even if a little).

I'm not so sure about this. A type assertion, except for the first time its done during a program execution, is only a couple instructions. Every time you'd need to do a type assertion with the interface{} approach (that is, you want to look at some piece of data in the tree), you'd have to do an array index with the subject of this thread.

 

- requires type assertions to use.

You can write some wrapper code for that, and this requires wrapper code as well. 

[David DENG]

I think the interface{} here is used as a safe pointer. Accessing the value is only a de-refference, while reading from an array is almost the same. For type checking, if the type to unbox is the same as the one in it, the checking can be optimized by the compiler to very efficient. maybe just an int comparing. This is compared to the proposed storing data in an array, in which case, deleting is not that efficient.

Compared to the map[int]data proposal, using interface{} should clearly be much more efficient and simpler.

David

[Jan Mercl]

On Mon, Feb 25, 2013 at 10:51 PM, John Asmuth <jas...@gmail.com> wrote:
>
>
> On Monday, February 25, 2013 4:43:09 PM UTC-5, Jan Mercl wrote:
>>
>> - make access slower (even if a little).
>
>
> I'm not so sure about this. A type assertion, except for the first time its
> done during a program execution, is only a couple instructions. Every time
> you'd need to do a type assertion with the interface{} approach (that is,
> you want to look at some piece of data in the tree), you'd have to do an
> array index with the subject of this thread.

I think that x86 has a single instruction bound check. I'd expect that
to be faster than type assertion. (However, measurements always beat
any speculations.)

>> - requires type assertions to use.
>
>
> You can write some wrapper code for that, and this requires wrapper code as
> well.

Well, I think the wrapper is not necessary in general. But I didn't
really read Nate's code. However, I like the interesting approach of
separation of the tree metadata from its content. It sacrifices
locality for generality. But it even allows for a single code to
handle memory and persistent variants easily. By coincidence I used
exactly that recently elsewhere. Even the "allocation" of the set
back-end can be made unified (same interface) with a real (disk file)
storage allocator, which made things even simpler.

-j

[Jan Mercl]

On Mon, Feb 25, 2013 at 11:00 PM, David DENG <david...@gmail.com> wrote:
> I think the interface{} here is used as a safe pointer. Accessing the value
> is only a de-refference, while reading from an array is almost the same. For
> type checking, if the type to unbox is the same as the one in it, the
> checking can be optimized by the compiler to very efficient. maybe just an
> int comparing. This is compared to the proposed storing data in an array, in
> which case, deleting is not that efficient.
>
> Compared to the map[int]data proposal, using interface{} should clearly be
> much more efficient and simpler.

Pretty possible, but that was not discussed by me in the relevant post
- the []T was. Again, one has to measure the performance, speculations
about performance can be wrong surprisingly often.

Anyway - it's the main point about Nate's tree design: no need for
interface{} (strongly typed) and still the same one code for any T
(modulo the one line declaring the T's back-end).

-j

[Dan Kortschak]

This is slightly off-topic, but I have a bugle in my hand.

Have you tried <http://godoc.org/code.google.com/p/biogo.llrb>?

It differs from GoLLRB in that:
* It's faster.
* Its API is more flexible, and IMO more idiomatic.
* It's extensively and systematically tested (not 100%).
* It implements *both* of Sedgewick's LLRB modes correctly.

[Nate Finch]

Why would you use something like this?

Completely type safe, you can't sneak a string into your tree of ints.

Also, the fact that the backing data is easily accessible in a slice (or map) can be handy when you want to do something with the data that isn't related to the tree structure, without having to traverse the tree to get at them.

And as others said, you can back this kind of a tree in a lot of different ways that make it more interesting than simple memory.

Mostly, I wrote it because it occurred to me that it was possible and to see in black and white how the API looks when it's written down.

As for speed, I don't know if it's faster or not. I might be able to come up with some benchmarks to compare it... as others said, the speed of type assertions isn't a huge bottleneck, but then again, neither is indexing an array.

I'm glad it's giving everyone something to talk about, without any proposed changes to the language ;)

[Jan Mercl]

Some numbers:

jnml@fsc-r630:~/src/tmp/bench/tree$ cat main_test.go
package main

import (
"math/rand"
"runtime"
"testing"
)

const N = 1e3

var (
keys = rand.Perm(N)
sum int
)

func BenchmarkSlice(b *testing.B) {
b.StopTimer()
s := make([]int, N)
runtime.GC()
b.StartTimer()
for i := 0; i < b.N; i++ {
for _, k := range keys {
sum += s[k]
}
}
}

func BenchmarkInterface(b *testing.B) {
var s interface{} = 42
for i := 0; i < b.N; i++ {
for _, _ = range keys {
sum += s.(int)
}
}
}

func BenchmarkMap(b *testing.B) {
b.StopTimer()
s := map[int]int{}
for i := 0; i < N; i++ {
s[i] = i
}
runtime.GC()
b.StartTimer()
for i := 0; i < b.N; i++ {
for _, k := range keys {
sum += s[k]
}
}
}
jnml@fsc-r630:~/src/tmp/bench/tree$ go version
go version devel +4b16fb118e08 Tue Feb 26 03:14:59 2013 +0800 linux/amd64
jnml@fsc-r630:~/src/tmp/bench/tree$ go test -bench .
testing: warning: no tests to run
PASS
BenchmarkSlice 500000 3443 ns/op
BenchmarkInterface 100000 22538 ns/op
BenchmarkMap 10000 159223 ns/op
ok tmp/bench/tree 5.897s
jnml@fsc-r630:~/src/tmp/bench/tree$

Note: Divide the numbers by N (1e3) to get the one loop pass + one
element access time (slice ~3.4 ns, interface{} ~22.5 ns, map ~159.2
ns).

-j

[Nate Finch]

I changed the data to strings just to see what would happen for values that don't fit in the interface.... this is what I got on win64 Core i7 2.2GHz:

package main

import (

"math/rand"

"runtime"

"testing"

)

const N = 1e3

var (

keys   = rand.Perm(N)

result string

)

func BenchmarkSlice(b *testing.B) {

b.StopTimer()

s := make([]string, N)

for i, _ := range s {

s[i] = "something non-trivial"

}

runtime.GC()

b.StartTimer()

for i := 0; i < b.N; i++ {

for _, k := range keys {

result = s[k]

}

}

}

func BenchmarkInterface(b *testing.B) {

var s interface{} = "something non-trivial"

for i := 0; i < b.N; i++ {

for _, _ = range keys {

result = s.(string)

}

}

}

func BenchmarkMap(b *testing.B) {

b.StopTimer()

s := map[int]string{}

for i := 0; i < N; i++ {

s[i] = "something non-trivial"

}

runtime.GC()

b.StartTimer()

for i := 0; i < b.N; i++ {

for _, k := range keys {

result = s[k]

}

}

}

C:\Users\nfinch\code\go\src\tmp\tree>go version

go version devel +e8cfa948baf2 Fri Jan 11 17:02:21 2013 +1100 windows/386

C:\Users\nfinch\code\go\src\tmp\tree>go test -bench .

testing: warning: no tests to run

PASS

BenchmarkSlice   1000000              1239 ns/op

BenchmarkInterface        200000             13395 ns/op

BenchmarkMap       50000             60000 ns/op

ok      tmp/tree        7.746s

again divide by 1000:  slice 1.2 ns/op, interface 13 ns/op  map 60 ns/op

The absolute values themselves are obviously not comprable, but the relative values are.  

When you're storing things that don't fit in the interface itself, it makes the assertion slower.

For ints, interface is 6.5x slower, for strings 10.8x slower than pure array indexing.

For reference, my numbers running Jan's benchmarks were about the same as his.

[Kevin Gillette]

On Monday, February 25, 2013 3:00:31 PM UTC-7, David DENG wrote:

I think the interface{} here is used as a safe pointer. Accessing the value is only a de-refference, while reading from an array is almost the same. For type checking, if the type to unbox is the same as the one in it, the checking can be optimized by the compiler to very efficient. maybe just an int comparing. This is compared to the proposed storing data in an array, in which case, deleting is not that efficient.

I tend to not consider a generalized interface{} based data structure, since even if it were more efficient (and often it won't be), and while it's simpler for the library author, compile-time verified type safety is far more important to me. I strongly believe many algorithms implementations, if carefully designed, can be written against self-describing data structures which the app programmer provides, rather than making the app programmer adapt their data to the algorithm.

[David DENG]

For sort, you are right. But the algorithm considering in this thread is different.

sort.Interface allowing the sort algorithm run on any list/array like algorithms. And sort algorithm itself does not generate extra data. Your data-structure is, e.g. a slice of structs. not the struct only. If sorting has to be done on a slice of interface{}, it is bad.

While in a binary tree algorithm, the data you are going to process are piles of elements separately. They have to be inserted into the tree one-by-one. Since you'd like to use the tree, you have to use the tree data-structure here(you data is embedded in), using interface{} or not.

interface{} is not a monster. I'm also curious about why unboxing it is obviously slower than accessing an element of an array.

David

[Jan Mercl]

On Tue, Feb 26, 2013 at 9:07 AM, David DENG <david...@gmail.com> wrote:
> interface{} is not a monster. I'm also curious about why unboxing it is
> obviously slower than accessing an element of an array.

I guess looking at the generated assembly code will give a clue. W/o
that I can only guess: slice access is N instructions (estimate: 3-5
?), type assertion (Go specs don't mention 'unboxing', so this is what
I guess you mean) is M instructions (estimate: 10+), M > N.

-j

[David DENG]

This only shows some problem of the compiler. Actually, the bottlenet is not there at all.

I made a direct comparison on the whole algorithm:

http://play.golang.org/p/7tyK7JZDvs (run locally)

package main

import (

"github.com/natefinch/tree"

"testing"

)

// StringData is just a slice that implements a comparison function

type StringData []string

// Cmp returns a closure that will compare the given string with

// the string located at an index of the underlying slice

func (s StringData) Cmp(val string) func(int) int8 {

// this is just a standard string compare based on the runes

return func(idx int) int8 {

other := []rune(s[idx])

for i, r := range val {

if i > len(other) {

return 1

}

c := r - other[i]

if c < 0 {

return -1

}

if c > 0 {

return 1

}

}

return 0

}

}

type Tree struct {

Val   interface{}

Left  *Tree

Right *Tree

}

// New Returns a newly initialized Tree.

func New() *Tree {

return &Tree{Val: nil}

}

// Insert adds the value to the tree.

//

// i is the key of the item in your datastructure

//

// cmp is a comparison function that should return

// -1 if less than data[i], 0 if equal, and 1 if greater than

func (t *Tree) Insert(v interface{}, cmp func(interface{}, interface{}) int8) {

if t.Val == nil {

t.Val = v

return

}

for {

switch cmp(t.Val, v) {

case -1:

if t.Left == nil {

t.Left = &Tree{Val: v}

return

}

t = t.Left

case 0, 1:

if t.Right == nil {

t.Right = &Tree{Val: v}

return

}

t = t.Right

default:

panic("Comparison function should only return 0, 1, or -1")

}

}

panic("impossible")

}

// Find returns the index of the item if it is in the tree or -1 if it is not.

//

// cmp is a comparison function that should return

// -1 if less than data[i], 0 if equal, and 1 if greater than

func (t *Tree) Search(v interface{}, cmp func(interface{}, interface{}) int8) interface{} {

t = t.search(v, cmp)

if t == nil {

return -1

}

return t.Val

}

func (t *Tree) search(v interface{}, cmp func(interface{}, interface{}) int8) *Tree {

if cmp == nil {

panic("Nil comparison function!")

}

for t != nil {

switch cmp(t.Val, v) {

case -1:

t = t.Left

case 0:

return t

case 1:

t = t.Right

default:

panic("Comparison function should only return 0, 1, or -1")

}

}

return nil

}

func Cmp(a, b interface{}) int8 {

other := []rune(b.(string))

for i, r := range a.(string) {

if i > len(other) {

return 1

}

c := r - other[i]

if c < 0 {

return -1

}

if c > 0 {

return 1

}

}

return 0

}

func BenchmarkSlice(b *testing.B) {

s := StringData([]string{"banana", "apple", "domino", "cat", "zebra", "monkey", "hippo"})

for i := 0; i < b.N; i++ {

t := tree.New()

for i, v := range s {

t.Insert(i, s.Cmp(v))

}

t.Search(s.Cmp("domino"))

}

}

func BenchmarkInterface(b *testing.B) {

s := StringData([]string{"banana", "apple", "domino", "cat", "zebra", "monkey", "hippo"})

for i := 0; i < b.N; i++ {

t := New()

for _, v := range s {

t.Insert(v, Cmp)

}

t.Search("domino", Cmp)

}

}

Using interface{} instead of index to a slice, I copy and then refactor the algorithm, closure is no longer needed, and the benchmark results:

BenchmarkSlice    200000             10505 ns/op

BenchmarkInterface        500000              6592 ns/op

David

[David DENG]

Write some sample lines:

var i int

var l []int = []int{1}

i = l[0]

LEAL    l+-44(SP),BX

CMPL    4(BX),$0

JHI     ,16

CALL    ,runtime.panicindex+0(SB)

MOVL    (BX),BX

MOVL    (BX),BP

var s interface{} = 1

i = s.(int)

MOVL    $type.int+0(SB),(SP)

LEAL    s+-28(SP),SI

LEAL    4(SP),DI

CLD     ,

MOVSL   ,

MOVSL   ,

CALL    ,runtime.assertE2T+0(SB)

MOVL    12(SP),DX

fmt.Println(i)

Assertion of type is done by calling to a function. Maybe the compiler can call the function before checking whether the type in the interface{} is exact the same as the specified may help.

David

[Jan Mercl]

On Tue, Feb 26, 2013 at 10:02 AM, David DENG <david...@gmail.com> wrote:
> This only shows some problem of the compiler.

Which problem you mean?

> Actually, the bottlenet is not

> Using interface{} instead of index to a slice, I copy and then refactor the
> algorithm, closure is no longer needed, and the benchmark results:
>
> BenchmarkSlice 200000 10505 ns/op
> BenchmarkInterface 500000 6592 ns/op

Your benchmark is flawed if your intent was to show interface{} is
better than []T (which you're not saying, actually). It's about, as
you're correctly pointing out, using a closure for the comparison or
not. Of course the later is faster, but it has nothing to do with,
again, []interface{} vs []T, where the later is proven to be faster.
This is actually the first time a had a look at Nate's code and the
closure approach is definitely not the optimal one. And that's exactly
what your benchmark proves.

I would suggest to shape the comparator function as: `cmp func(a, b
int) int`, where a and b are indexes/handles which contents should be
compared. At insert, the item get's an index/slot _before_ that index
being put in a new tree node at the proper place of the tree. For
search I would probably "waste" a well known index like, say 0.

Then I'd expect the []int, []string, ... to beat the []interface{} at any time.

-j

[Kevin Gillette]

On Tuesday, February 26, 2013 1:07:19 AM UTC-7, David DENG wrote:

While in a binary tree algorithm, the data you are going to process are piles of elements separately. They have to be inserted into the tree one-by-one. Since you'd like to use the tree, you have to use the tree data-structure here(you data is embedded in), using interface{} or not.

It's fairly common practice, even in other languages, to represent non-flat datastructures using flat containers, by putting the abstraction in the algorithm, as Nate Finch has done here. See <http://docs.python.org/2/library/heapq.html>, for example, which utilizes python lists as the underlying container. Python, however, does not always favor building on existing container types: an example of this is containers.deque, which is designed for efficiency in primitive operations (no emphasis on high level organization), whereas something like heapq is concerned with high-level behavior.

Many of the algorithms you're alluding to are concerned with high-level organization, not primitive ops like efficient front-insertion behavior, and so there's considerably less benefit in making Go implementations of these algorithms be concerned with the low-level organization of the data.

Additionally, and importantly, any conventional data structure relying on pointers or inter-node references can be represented with indexes into a flat array/slice. Linked lists, for example, can trivially be represented using []int alone, where the value of each index is the next index in the list. Using a contiguous list also has considerable empirical evidence indicating that they are much more allocation and cache-efficient (and thus faster) than independently allocated nodes, so the discipline put toward maintaining the separation of algorithm and data, while not actually much effort on the part of the application programmer, can have non-obvious performance benefits in addition to compile-time safety. Even for constantly growing dataset, it has been demonstrated in general, that caching cpu architectures favor (in terms of performance) copy-to-grow lists up to ~1 million elements in size, much higher than many programmers would expect, instead of pointer-heavy structures that didn't happen to be batch allocated.

[David DENG]

I never expect interface{} being faster than []T. That is impossible and maybe meaningless to the problem discussed in this thread. Even if the single accessing to []T is fast, the corresponding algorithm runs slow.

My point is: If interface{} is the right thing for the algorithm, just use it.

I still cannot figure out a better algorithm using current data-structure than the one using interface{}, when you need to remove a node from the tree.

David

[Jan Mercl]

On Tue, Feb 26, 2013 at 11:09 AM, David DENG <david...@gmail.com> wrote:
> I never expect interface{} being faster than []T. That is impossible and
> maybe meaningless to the problem discussed in this thread. Even if the
> single accessing to []T is fast, the corresponding algorithm runs slow.

That has not been proven and I would be surprised by such outcome.
It's not the algorithm but the API design, using an unnecessary
closure, where the slowdown is rooted.

> My point is: If interface{} is the right thing for the algorithm, just use
> it.

Agreed. So as: Don't use interface{} where you can get complete type
safety at compile time, even with improved run time performance.

-j

[David DENG]

heap surely uses list/array. But that does not mean all data should be stored in a list.

Your general statment may be right, but let's sit down and see this specific case: to generate a search tree. Storing all nodes in a slice, and using the index to reference an element is just same as using allocating by the system(one-by-one, or a slice of elements, make(T[], N)), and use the pointer to reference an element. So use unsafe.Pointer? No, the name unsafe frightened me. Ok, here comes interface{}. It is slower than unsafe.Pointer, since it checks the type. But maybe that doesn't matter.

Why not use index+slice? how do you delete a node?

What if the elements are established once and read (search) only? Why not sort them and use the binary-search algorithm?

Some of the above statements may be too absolute, but I just wanna discuss algorithms.

David

[Nate Finch]

On Tuesday, February 26, 2013 4:30:13 AM UTC-5, Jan Mercl wrote:

This is actually the first time a had a look at Nate's code and the
closure approach is definitely not the optimal one. And that's exactly
what your benchmark proves.

I would suggest to shape the comparator function as: `cmp func(a, b
int) int`, where a and b are indexes/handles which contents should be
compared. At insert, the item get's an index/slot _before_ that index
being put in a new tree node at the proper place of the tree. For
search I would probably "waste" a well known index like, say 0.

Then I'd expect the []int, []string, ... to beat the []interface{} at any time.

Yeah, note that this is a proof of concept, not at all optimized. I wrote it yesterday morning before work. Definitely did not expect people to be benchmarking it :)

I think using the two indexes on insert is a very good optimization, since there's no drawback. But for search, "wasting" an index on the search means you're restricting reads to be single threaded. I guess we could throw this in with the int64 optimization and just throw away indexes when we search (there's opportunity to recover the wasted key if we finish the search and see that no one has "used up" the next-highest index).

 As for using interface{} or not... The whole point of this was to NOT use interface{}. Yes, you can trivially use interface{} in your tree structure. That's easy. It also requires runtime type checking, which I try to avoid when possible, because it can mean that errors are missed until the product is running.. which is never a time when I want to find out something fails.

I honestly never even considered performance. The fact that my crappy implementation is at all performant is kind of surprising to me :) 

[Dan Cross]

It seems that Nate's purpose in writing this code was as much to show that it could be done as to do it.  Everyone involved knows that one can use interface{} to build a search tree, but that was not the point.  So why keep telling him to use interface{} when the whole point of the exercise was to show that one could do it *without* using interface{}?

--
You received this message because you are subscribed to the Google Groups "golang-nuts" group.
To unsubscribe from this group and stop receiving emails from it, send an email to golang-nuts...@googlegroups.com.
For more options, visit https://groups.google.com/groups/opt_out.
 
 

[Nate Finch]

On Tuesday, February 26, 2013 7:47:13 AM UTC-5, Nate Finch wrote:

I guess we could throw this in with the int64 optimization and just throw away indexes when we search (there's opportunity to recover the wasted key if we finish the search and see that no one has "used up" the next-highest index).

Wow.. I need to wait until the coffee kicks in before replying I guess. The int64 key with throw-away indices was for use with a map... so, while that's fine if your backing datastore is a map, it's not really applicable if your backing datastore is a slice.

You could just append the item you want to search for to the slice, and do the i,j index comparison that way, but then you have to worry about cleaning up the temporary item... if no one has inserted after you, it's easy, if someone has, then we're back to the compacting problem.

[Steven Blenkinsop]

Leave this decision to the data. It might just use append, as you suggest. Or it could reserve -1 to point to an element that each goroutine has its own copy of. Insertion and removal have to happen at the tail, since you need 0 based contiguously indexable data, but otherwise it's up to the datastructure to assign indexes to things. Of course, insertion and removal can't happen in parallel.

[Nate Finch]

This is a good point, though implementing one or two example standard solutions is probably a good idea.  But I guess I could do it each way and let the implementer of the backing data decide what tradeoffs they want to make.

 

[Nate Finch]

It occurs to me that the closure solution could be replaced trivially with something like this:

type StringData struct {

    Data []string

    CmpTarget string

    CmpIndex int 
}

The compare function passed into Tree could then be a standard function on StringData that either references the index of a value (for Inserts since they're already in the backing data) or compares vs. the value in CmpTarget (for searches of external values).

This would remove the whole closure nonsense from the equation, and would make the performance significantly faster.  It does make searches only possible from a single goroutine (inserts too, but they should be anyway).

[Vanja Pejovic]

if you create a separate StringData for every search, could you do concurrent searches?

[Nate Finch]

FYI, I rewrote the tree API so that you don't have to pass it a closure... instead it's in sort.Interface style, where you pass in an interface with an i, j compare method, so you don't have to create and copy a closure for every search.  This makes inserts trivial, searches for values not in the 

Docs here: http://godoc.org/github.com/natefinch/tree

I added benchmarks for my code in github.com/natefinch/treesample.  I modified David's interface tree to match the new structure of treesample (so the comparison is fair), that code is here: http://play.golang.org/p/Vl3O3A2O-g

I also updated the benchmarks so they much more narrowly test insert and search (whereas before they were testing tree construction, multiple inserts, and a find).

The time to insert / search is pretty close for interface vs. slice implementations, though slice is still a little faster.

BenchmarkInterfaceInsert         1000000              1974 ns/op

BenchmarkInterfaceFind   1000000              1320 ns/op

BenchmarkInsert  1000000              1606 ns/op

BenchmarkFind    1000000              1036 ns/op

[David DENG]

no git push for treesample? I have a question: you have to append(and delete in the end) a string to the slice just for finding it?

Besides, I suggest the benchmark part should be modified to like this:

func BenchmarkInterfaceInsert(b *testing.B) {

    for i := 0; i < b.N; i++ {

        b.StopTimer()

        t := makeTree()

        b.StartTimer()

        t.Insert("pineapple")

        t.Insert("grape")

        t.Insert("cherry")

    }

}

func BenchmarkInterfaceFind(b *testing.B) {

    b.StopTimer()

    t := makeTree()

    b.StartTimer()

    for i := 0; i < b.N; i++ {

        t.Find("monkey")

        t.Find("hippo")

    }

}

This makes the timing more accurate thus more stable.

David

[Nate Finch]

Just did the git push... sorry about that. I guess I did tree and not treesample.

[David DENG]

I implement another version using unsafe.Pointer: http://play.golang.org/p/7ltuWR_fmZ (This is a toy, should not be used in practice)

I run the benchmark(modifed as I suggested for more accurate timing):

BenchmarkInsert  500000      3270 ns/op

BenchmarkFind 1000000      1639 ns/op

BenchmarkInterfaceInsert  500000      4175 ns/op

BenchmarkInterfaceFind 1000000      2156 ns/op

BenchmarkUnsafeInsert 1000000      2609 ns/op

BenchmarkUnsafeFind 1000000      1609 ns/op

The possible conclusion is: type assersion of interface{} did cause some efficiency problem to some extent, but I think that can be optimized in the new compiler.

David