Type func binding and interfaces

[Louki Sumirniy]

I essentially am trying to find an effective method in Go, preferably not too wordy, that lets me create an abstract data type, a struct, and a set of functions that bind to a different data type, and that I can write, preferably not in too much code, a change that allows the data type of the embedded data to be changed. It's basically kinda inheritance, but after much fiddling I found a hackish sorta way that isn't *too* boilerplate filled:

type nullTester func(*Bast, uint32) bool

type Bast struct {

  ...

  isNull    nullTester

  ...

 }

func isNull(b *Bast, d uint32) bool {

  return d == 0

}

func NewBast() (b *Bast) {

  ...

  b.isNull = isNull

  ...

}

// IsNull - tests if a value in the tree is null

func (b *Bast) IsNull(d uint32) bool {

  return b.isNull(b, d)

}

Now, bear in mind I haven't shown all of the code. But there is a slice array in the Bast struct, and I it is defined as an interface{} and isNull is one of a set of operators that have to be written to match the type used in the slice store, this might be a bad example because it doesn't actually act on the interface typed slice, but the point here is just this:

It does not appear to be possible to make the type specification from the top line match the function signature of the type-bound function in the bottom of the code snippet. I haven't been able to find anything that shows that a func type can have a method binding.

https://github.com/calibrae-project/bast/blob/master/pkg/bast/bast.go is where my WiP lives. This slightly hacky solution seems sound to me, I just don't like to be forced to use workarounds like this. If a type signature cannot be written that matches a method, yet I can do it this way, I don't see what purpose this serves as far as any kind of correctness and bug-resistance issues go. I would have to deal with a lot more potential bugs if I had to concretely implemennt this library for the sake of 1 slice and 7 functions out of a much larger library that conceptually is intended to only deal with comparable, mainly numerical values anyway.

[matthe...@gmail.com]

Interface types are useful when the data structure is varied. Why not an interface containing these varying functions as methods instead of function types?

Matt

[Louki Sumirniy]

You will see in the code I linked in the previous message that I already do have the interfaces in there. They can't be bound to the struct directly because I can't specify a function type that matches the signature, thus the use of a wrapper, and the interface types in the parameters.

I just can't override them, and the great bulk of the code is not these small set of initialiser/allocator/comparator/getter/setter functions, so to have to search and replace through the whole thing, and maintain multiple nearly identical pieces of source code for the sake of 7 functions that are all very short, and differ between these versions, when everything else is the same... then I find a bug in one version, in the outer shell of the code and I have to merge every change of it into the other 5 versions... it's extremely cumbersome. 

The solution I have shown is just the first thing that looks to me like it would work. I have read tons of tutorials about composition and polymorphism and embedding in go, and in the end I pieced this together from several different things I learned. I tried several different things. It just makes absolutely no sense to have to go through and add a load of maintenance work to my code just so I can create, expand, read, write and compare values stored within the otherwise identical data structure.

[Louki Sumirniy]

https://github.com/golang/go/issues/24996#issuecomment-383424588

It seems that (Type).FuncName in the assignment binds to the struct... I am glad I found an answer so quickly because my hackish solution was gonna be implemented today.

[Louki Sumirniy]

I spent two hours wrestling with this, but as you can see in this playground, the method I proposed totally works: https://play.golang.org/p/FMvisWS9tuP

I propose that the type builtin when dealing with functions should have an extension made to it to add the method binding to the type signature so this workaround is not necessary. It would not break the spec, old code, or any of the goals that Go works towards. It would actually help with getting adoption by OOP programmers, in my view, because method overriding for this exact purpose of enabling the abstraction of backend type stuff (in my case it's just an array, but it could easily be a storage protocol or network protocol) would help immensely in implementing pluggable architectures.

[matthe...@gmail.com]

This is a code smell for me:

type BAST interface {
    AddRow() error
    IsLeft(interface{}, Cursor) bool
    IsRight(interface{}, Cursor) bool
    IsEqual(interface{}, Cursor) bool
    IsEmpty(Cursor) bool
…

Interfaces should be small. This looks like a class definition which isn’t a Go pattern. Also I would avoid interface{} if possible, and the function types seem more complicated than necessary. I’m not convinced your types/API are optimal.

I still don’t exactly understand the goal, but this is my thinking about the playground example: https://play.golang.org/p/KNdrYbebpuo

Matt

[Louki Sumirniy]

I did look at the Red/Black tree on Github and that was what got me started. But you need to understand exactly why those functions seem great in number. First of all, of course you could swap out 3 of those comparators for 1, and you probably don't even get why there is the 'empty' one. The datatype uses zero as a null value, as it is aimed at hashes and pretty much nothing hashes to zero (99.99999999% to understate it). 

In the code the caller would have to use, and this starts with my own code, so I am considering my own capacity to decode my code versus writing it in such a way that it is simple to understand. If I collapse those three functions into one, I either have to define a set of constants to put a human readable name on it - or, for a very small cost of maybe 10-15 bytes extra, human can read the code and know what it does and why it isn't incorrect. When you look further down to see what these functions are actually implemented with, you'll discover they are mostly one-liners. On the micro scale, it might seem making separate calls for these is a waste. But on the other side, if my caller code has to run a 3 level or longer if/then or switch/case, did I, as the programmer of the library, do my users (my fellow programmers) any favours? Nope!

With this, the user can just say 'b.IsLeft(number, cursor)'. Sure, maybe there is no point in even having more than two conditions, since !IsLeft is the same as IsRight. But what if I wanted to descend the sort order. Then my code is riddled with '!IsRight' while I am trying to travel left. It's not good for the reader, and not good to read is hard to maintain, hard to maintain is expensive, and probably will be replaced by something else later. Reusability is very important for low level functions. It would be better for everyone if someone did the job right, first time, and for a long time afterwards, everyone can depend on it.

And coming back full circle to how I came up with this, it was precisely by reading the cryptic and difficult to understand code of others, like that Red/Black tree. Computer programming is a heavy cognitive load task as it is. Arbitrary concepts of efficiency that don't take account for the cost of decoding the results of this theory tend to lead to reinventing the wheel, because the wheel was too cryptically constructed to simply modify it.

</rant>

The IsNull function is actually just a way of implementing x == 0. But I don't want to tie my users down to integers and floats. What if they want to sort strings? What if they want to sort complex numbers, matrixes, or what have you? I can't overload the equality operator, and even if I could, then there would be the issue of type inference, implicit casts, or the wordiness of explicit casts. Instead, the IsNull is already typed to the data you want to work with, it can have something other than zero as its null sentinel, or in other words, my slightly wordy interface means your sleek, svelte application that is easy to debug.

[matthe...@gmail.com]

But I don't want to tie my users down to integers and floats. What if they want to sort strings? What if they want to sort complex numbers, matrixes, or what have you?

This is what the interface concept was made for.

Why would the implementation of IsLeft be different if the BAST data is organized another way? I think the abstraction you're expressed isn't narrow enough.

I don’t know the BAST details, but why not start here?

type Node struct {
    Element
    Left  *Node
    Right *Node
}

func (a Node) LeftEqual() bool {
    if a.Left == nil {
        return false
    }
    return a.Equal(a.Left.Element)
}

type Element interface {
    Equal(Element) bool
    Null() bool
}

Matt

[Louki Sumirniy]

First issue is that BAST does not use references. This is so that searches proceed linearly through memory. Instead it uses a flat array that it cuts into sequentially doubling sized rows, representing the slots that a binary tree has.

Secondly, you just complicated my design even further with 'is left equal'. why not just 'go left' 'is this equal'?

The implementation of the comparison could be different for all kinds of reasons. Number one reason that is already on my plan of action is where I have an arbitrary bit-width data, say 64 bits, but I want to sort one tree by the first 32 bits, and the same data feed into another tree at the same time that searches/sorts by the second 32 bits. This is the main reason for needing this flexibility. Mainly I want to stick to small blobs of memory, just numbers, mostly, but that at least includes 256 bit values. Much beyond that will destroy the advantage of this scheme, in that the tree will be too big in memory because of how large the probably 1/4 to half-filled node collection will generally be.

[matthe...@gmail.com]

Is the need for a memory efficient implementation backed by a performance profile?

Matt

[roger peppe]

On 22 April 2018 at 23:20, Louki Sumirniy

I don't really understand why you think you want all those function types.
Your code seems to mix concerns quite a bit, but interfaces in Go are generally
closely focused on a particular thing.

I don't understand anything about your algorithm, but ISTM you could
do something like this:

https://play.golang.org/p/wv0T8T8Ynns

Some changes I made in doing that;

- unexported a load of identifiers that really don't deserve to be
part of the public API
- made Cursor into a lightweight by-value type
- defined a Store interface that doesn't require knowledge of the
Cursor data type.

A few other observations:

- requiring a value type to know whether an item is null or not does
not seem great
when you're storing integers - who is to say that the zero uint32 is
not a valid thing to store?

- requiring callers to know about AddRow (and hence how the tree is
organised) does
not seem ideal.

- there's no way to search for or insert items, but I guess you'll be
doing that later.

- it looks like your algorithm will always use a power-of-two multiple
of the element size,
which could end up very inefficient when the tree is large.

cheers,
rog.

[Louki Sumirniy]

The type function bindings are not the problem, the problem is the fact that despite in every other way the signatures match, they will not be found by the compiler to bind to the type, and thus the need to wrap the invocations. 

I maybe should explain that I have had some experience programming with Vala, which I suppose borrows something from C#, a competitor to Go, that in my opinion mostly goes too far on the OOP side, but in Vala, it was something that eventually pretty much put me off the language, having to specify in many library functions 'bound' variables as parameters, 'in' and 'out'. The code I have written essentially follows this model. I don't like this model, and I like how Go otherwise allows the flexibility of composition, but it puts this artificial barrier up against polymorphism.

Note that another area that is very similar in its intent is the way that you can't bind slices to interfaces. Having already figured out the above problem, it only took me about an hour to figure out how to encapsulate the slice in a struct and bypass this limitation. 

What puzzles me though, is why anyone thinks that it should be made so complicated to simply allow a DATA STORAGE library to switch out different back-store types is a good thing.

As for your points:

I set many of those identifiers to export because I wanted to keep separate derived libraries that replaced the storage types embedded into the main library. These limitations would not exist were the 'back store' over the wire or on disk. They only exist for the storage that is most accessible to the program, the main memory.

Regarding the use of zero as an nil, that is already accepted by numerous built in types (error, for example), and in this case the reason why I have put that into the *abstract* type is because the data I am writing this algorithm for is hashes, which are never zero, at least in practise, over a period of decades, no hash functions produce zero out of any significant amount of known data.

This idea that I should be hiding all the functions smells like OOP to me. As it stands with how it has to be implemented in Go, the accessing of these would-be-private-in-C++ scenario, is very cumbersome due to the need to use type assertions. I have tinkered with this for educational value but I don't want to have to deal with this in the actual implementation. A key insight of Schneier's work is 'security by obscurity' is weak. Private functions fit that maxim pretty well. I think that there is no real benefit in doing this, since after all, this is the source, and if you can be told you can't access that thing that is 'private' then it's not terribly private in reality, only for arbitrary philosophical reasons excluded from your programmatic access without forking the code.

The search functions are already in there, it's a piece of cake, given the ability to test for equality, lesser and greater. That was probably one of the first things I implemented, because it's so simple. Nobody has ever implemented a binary search tree with a dense store like this before, and so the insert and delete functions are not there yet. Just use your imagination for a little bit, even with a 4 row *dense* tree and consider what happens when I delete a node with children, let's say, at row 3, with two children. Where do thtose children go? They are now orphans, as their parent has been cut out of the tree. So, and critical to the design of BAST, is that it be possible to perform short optimisations during delete/insert write operations that do not cost too much time, but at the same time, do not cause the search cost to become excessively spread out, and specifically with delete, you can't have orphans. They have to be pushed up and inwards, it's not complicated, but it gets more complicated the more nodes are children of the severed node.

It's not a model for tree structures that ANYONE is familiar with. Unlike simple, stupid newbie mistakes, this is intentional. I am writing this algorithm because it, by its architecture, reduces random access of memory, and in this, it gains a benefit of reduced cache misses in the CPU and thus will have, potentially, a serious performance advantage compared to any search-and-sort algorithm whether it be hashtables or vector reference based binary search trees.

Yes, on the last point, it always uses power of two because it is modelling a dense binary tree, hence the name 'Bifurcation Array'. Thus also why I haven't finished the insert/delete functions. You can't just spin things around like in a vector based BST. There is a cost in search linearity for the differentials of path lengths from the root, but here's the thing - if you want to dodge allocating a new row, you could instead find the value that you could push inwards to the other side, and trace a path until there is an inner empty child that you can 'rotate' into. Most of the time this will not exceed maybe 32kb of data, maybe at the most, most of the time, for most sizes of trees you would be working with, no more than 1mb, and guess what, that all fits within a CPU cache which means manipulating that memory takes no wait time and data transfers at 4-6 times as fast as the front side bus.

For the same reason I have functions and variables that track the fill of each row of the tree, as well as one at the top that totals the left and right. These values can be quickly updated with each insert and delete, and can be used to feed heuristics that decide what probably will be the best way to shuffle the tree around to maintain its low variance of minimum and maximum search time.

It's for realtime hash tables that rapidly change, it's for proof of work algorithms that would otherwise entail such a high and mostly fixed cost of sorting to restructure to enable fast searching, so that after each operation, the tree is in a fairly optimal state for searches, as well as inserts and deletes.

I might be talking in ways that more experienced programmers and CS people may think to be naive, but I don't think it is naive to think that we can make more hay out of the SRAM in CPU caches, especially for applications that are becoming extremely critical to our lives. Databases specifically, but as a cryptocurrency miner, the issue of the onslaught of ASICs has given me a personal and visceral motivation to try and find a way to eliminate the differential between specialised hardware and commodity CPUs. It's an interesting fact that isn't really discussed much, that the architecture of CPUs is precisely a database specific design. There has been some progress in using GPUs to accelerate graph databases, which involve graphs (and vectors, and variant payload data types), but this is almost completely irrelevant to how SQL, NoSQL and K/V database (and DHT based) stores work, and the greatest amount of interesting stuff happening these days in computer systems is all around distributed systems, an area that is rarefied amongst the rarified field of CS itself.

Sorry if I went off on a rant there, but I hope it explains why I am posing questions and asking for advice from more experienced gophers about how to do these things. The body of material available with the use of google searches came up with almost nothing, and nothing that directly addressed my modelling and even reading closer at the code that appeared to implement this datatype agnosticism (within the constraint of comparability and an nil value) so I wanted to engage people in a discussion. I would be very pleased to learn that I have missed important things in the field that render my design useless. I first was studying OOP back in the early 90s, and it seemed like some kind of magic, but anyone who is reading this probably already agrees that OOP (and functional) are not panaceas and languages like Go are addressing this issue, promoting correctness, maintainability, and efficiency all at the same time. I have tangled with more OOP code than I wish I ever had, and to disclose, I did quite a bit of BASIC and Assembler coding in my youth and you never forget the thrill of discovering a property in the numbers or the architecture that lets you shortcut to solve previously messy, thick and dense problems that faced programmers in the past.

[Jan Mercl]

On Mon, Apr 23, 2018 at 8:58 PM Louki Sumirniy <louki.sumir...@gmail.com> wrote:

> The type function bindings are not the problem, the problem is the fact that despite in every other way the signatures match, they will not be found by the compiler to bind to the type, and thus the need to wrap the invocations. 

I understand all the words, can parse the sentence easily, but still have no ... idea what you're saying. Even after guessing that most probably by 'type function binding' you mean simply a method.

Using well defined terms, appearing in the language specification, can make the ideas communicated much more comprehensible to others.

--

-j

[roger peppe]

On 23 April 2018 at 19:58, Louki Sumirniy

<louki.sumir...@gmail.com> wrote:
> The type function bindings are not the problem, the problem is the fact that
> despite in every other way the signatures match, they will not be found by
> the compiler to bind to the type, and thus the need to wrap the invocations.
>
> I maybe should explain that I have had some experience programming with
> Vala, which I suppose borrows something from C#, a competitor to Go, that in
> my opinion mostly goes too far on the OOP side, but in Vala, it was
> something that eventually pretty much put me off the language, having to
> specify in many library functions 'bound' variables as parameters, 'in' and
> 'out'. The code I have written essentially follows this model. I don't like
> this model, and I like how Go otherwise allows the flexibility of
> composition, but it puts this artificial barrier up against polymorphism.
>
> Note that another area that is very similar in its intent is the way that
> you can't bind slices to interfaces. Having already figured out the above
> problem, it only took me about an hour to figure out how to encapsulate the
> slice in a struct and bypass this limitation.

You can bind slices to interfaces, although you'll need to define a
new slice type and some methods if you want it to do anything
slice-specific.

> What puzzles me though, is why anyone thinks that it should be made so
> complicated to simply allow a DATA STORAGE library to switch out different
> back-store types is a good thing.

I don't understand why you think it's so complex to do this. If you
look at the code I posted, you'll see that the Store type is very
straightforward to implement - most of the code could even be
generated automatically in fact.

> As for your points:
>
> I set many of those identifiers to export because I wanted to keep separate
> derived libraries that replaced the storage types embedded into the main
> library. These limitations would not exist were the 'back store' over the
> wire or on disk. They only exist for the storage that is most accessible to
> the program, the main memory.

I don't understand this. If you're replacing the underlying storage
types, why would you need to export details of an algorithm that the
storage types shouldn't need to have anything to do with?

> Regarding the use of zero as an nil, that is already accepted by numerous
> built in types (error, for example), and in this case the reason why I have
> put that into the *abstract* type is because the data I am writing this
> algorithm for is hashes, which are never zero, at least in practise, over a
> period of decades, no hash functions produce zero out of any significant
> amount of known data.

Why does your algorithm need to know about the possible nil-ness of
the stored items? It doesn't use that property now, at any rate.

> This idea that I should be hiding all the functions smells like OOP to me.

This isn't OOP - it's just good code hygiene. By hiding implementation
details, you make the public interface clear and you prevent clients
from relying on internal implementation details that you might want to
change.

> As it stands with how it has to be implemented in Go, the accessing of these
> would-be-private-in-C++ scenario, is very cumbersome due to the need to use
> type assertions. I have tinkered with this for educational value but I don't
> want to have to deal with this in the actual implementation. A key insight
> of Schneier's work is 'security by obscurity' is weak. Private functions fit
> that maxim pretty well.

Private functions are not "security by obscurity". Private functions
aren't "obscure" (you can see them in the source perfectly well) but
they are "secure" because you cannot access them.

> I think that there is no real benefit in doing this,
> since after all, this is the source, and if you can be told you can't access
> that thing that is 'private' then it's not terribly private in reality, only
> for arbitrary philosophical reasons excluded from your programmatic access
> without forking the code.

As above, doing this is considered good code hygiene. If you do decide
to fork the code and make something public, then it's obvious that
you're breaking the API boundaries.

> The search functions are already in there, it's a piece of cake, given the
> ability to test for equality, lesser and greater. That was probably one of
> the first things I implemented, because it's so simple. Nobody has ever
> implemented a binary search tree with a dense store like this before, and so
> the insert and delete functions are not there yet. Just use your imagination
> for a little bit, even with a 4 row *dense* tree and consider what happens
> when I delete a node with children, let's say, at row 3, with two children.
> Where do thtose children go? They are now orphans, as their parent has been
> cut out of the tree. So, and critical to the design of BAST, is that it be
> possible to perform short optimisations during delete/insert write
> operations that do not cost too much time, but at the same time, do not
> cause the search cost to become excessively spread out, and specifically
> with delete, you can't have orphans. They have to be pushed up and inwards,
> it's not complicated, but it gets more complicated the more nodes are
> children of the severed node.
>
> It's not a model for tree structures that ANYONE is familiar with.

I think you overestimate the novelty of your algorithm. It sounds to
me like it bears significant resemblance to a "complete binary tree"
(see https://xlinux.nist.gov/dads/HTML/completeBinaryTree.html).

> Unlike simple, stupid newbie mistakes, this is intentional. I am writing this
> algorithm because it, by its architecture, reduces random access of memory,
> and in this, it gains a benefit of reduced cache misses in the CPU and thus
> will have, potentially, a serious performance advantage compared to any
> search-and-sort algorithm whether it be hashtables or vector reference based
> binary search trees.

You keep on making references to the efficiency of this algorithm, but
I don't see any benchmarks or algorithm analysis that supports your
viewpoint here.

cheers,
rog.

> --
> 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/d/optout.

[Louki Sumirniy]

On Tuesday, 24 April 2018 11:15:34 UTC+3, rog wrote:

On 23 April 2018 at 19:58, Louki Sumirniy
<louki.sumir...@gmail.com> wrote:

 

> I set many of those identifiers to export because I wanted to keep separate
> derived libraries that replaced the storage types embedded into the main
> library. These limitations would not exist were the 'back store' over the
> wire or on disk. They only exist for the storage that is most accessible to
> the program, the main memory.

I don't understand this. If you're replacing the underlying storage
types, why would you need to export details of an algorithm that the
storage types shouldn't need to have anything to do with?

Because if they can't be accessed outside of the scope of the file I am forced to add the alternative data types within the same file. This is a massive loss of flexibility (and means an importing application cannot implement its own variant). In my test/scratch/thingy, even within the same folder direct access was impossible because of file scoping, so I capitalised the fields, because if it can't be done even in the same folder, in a different pkg/name folder for another implementing library I won't be able to do this either

 

> Regarding the use of zero as an nil, that is already accepted by numerous
> built in types (error, for example), and in this case the reason why I have
> put that into the *abstract* type is because the data I am writing this
> algorithm for is hashes, which are never zero, at least in practise, over a
> period of decades, no hash functions produce zero out of any significant
> amount of known data.

Why does your algorithm need to know about the possible nil-ness of
the stored items? It doesn't use that property now, at any rate.

Zero is the default signifier of an empty node. Zero acts as the sentinel for the search to detect when it has fallen off the edge of a branch. But zero isn't necessarily the 'empty node' value, an implementation using strings needs to compare to "", and struct and slice types would need to test for nil, and one may conceive of an application where the empty field sentinel actually has a value (and its initialisation would require filling the data that way, of course)

 

> This idea that I should be hiding all the functions smells like OOP to me.

This isn't OOP - it's just good code hygiene. By hiding implementation
details, you make the public interface clear and you prevent clients
from relying on internal implementation details that you might want to
change.

How do I override the functions to implement the data abstraction if the overridden functions are not exported? Internal implementation details for this specific library will not change once I hit the beta milestone. This is not a complex application, it is just a data storage/search library. Somewhere along the line there will have to be some exported elements that can be passed to and fro and possibly some of these will be encapsulated like this. But encapsulation can be a big obstacle to reuse and derivation.

Specific points that clearly do not need to be visible need to be pointed out. If someone is *extending* this then to be honest, they should just be forking it anyway, rather than importing it. Also, I don't think that is as easy to do in Go as it would be in an OOP language, as I had to do very specific things in the base type struct spec in order to enable overriding. In an OOP language you can override until the cows come home, and this is the 'fragility' problem of OOP classes that Go spsecifically aims to eliminate by enforcing composition.

If a user of the library were to embed the structure in another type, they would get access to these private elements anyway, and then by doing this on an import rather than a fork, they would be depending on me not to change the way it works. Everything I have exposed is specifically exposed to allow an external library to simply reimplement the set of accessors. These accessors need to know the Cursor type also, as this is how the tree is walked.

If I was writing a much more complex library then clearly there needs to be exposure of only that which is interface, and the interface needs to be immutable until version bumps.

 

> As it stands with how it has to be implemented in Go, the accessing of these
> would-be-private-in-C++ scenario, is very cumbersome due to the need to use
> type assertions. I have tinkered with this for educational value but I don't
> want to have to deal with this in the actual implementation. A key insight
> of Schneier's work is 'security by obscurity' is weak. Private functions fit
> that maxim pretty well.

Private functions are not "security by obscurity". Private functions
aren't "obscure" (you can see them in the source perfectly well) but
they are "secure" because you cannot access them.

This is nonsense because all I have to do is fork and expose and what exactly is the nature of the danger of me knowing the internals? I follow FP methodology fairly strictly whenever possible and I did not design this library with it in mind to multi-thread it and expose the matter of side effects and conflicting state changes. It's specifically designed to be single threaded.

 

> I think that there is no real benefit in doing this,
> since after all, this is the source, and if you can be told you can't access
> that thing that is 'private' then it's not terribly private in reality, only
> for arbitrary philosophical reasons excluded from your programmatic access
> without forking the code.

As above, doing this is considered good code hygiene. If you do decide
to fork the code and make something public, then it's obvious that
you're breaking the API boundaries. 

You are probably right about a few parts of this needing to be not exported. Specifically anything that cannot be extended, such as the tree balance functions, and the details they work with, the fill tracking array, and probably the depth and length values should be also not exported, as one thing that would totally screw up this algorithm is callers clobbering those state values, and triggering errors (I do test for all such conditions that would cause array bounds exceptions, though, and this would be the fault of the consumer). It's still a work in progress. I mean, I only just finally made a working implementation for the abstraction of the backing store yesterday. I'm not a professional OOP language programmer, or any kind of professional, this is a work of love and that I think will help me achieve goals for future projects, at least with a high likelihood for the next project on my agenda.

 

> The search functions are already in there, it's a piece of cake, given the
> ability to test for equality, lesser and greater. That was probably one of
> the first things I implemented, because it's so simple. Nobody has ever
> implemented a binary search tree with a dense store like this before, and so
> the insert and delete functions are not there yet. Just use your imagination
> for a little bit, even with a 4 row *dense* tree and consider what happens
> when I delete a node with children, let's say, at row 3, with two children.
> Where do thtose children go? They are now orphans, as their parent has been
> cut out of the tree. So, and critical to the design of BAST, is that it be
> possible to perform short optimisations during delete/insert write
> operations that do not cost too much time, but at the same time, do not
> cause the search cost to become excessively spread out, and specifically
> with delete, you can't have orphans. They have to be pushed up and inwards,
> it's not complicated, but it gets more complicated the more nodes are
> children of the severed node.
>
> It's not a model for tree structures that ANYONE is familiar with.

I think you overestimate the novelty of your algorithm. It sounds to
me like it bears significant resemblance to a "complete binary tree"
(see https://xlinux.nist.gov/dads/HTML/completeBinaryTree.html).

A complete binary tree does not have a concept of empty nodes. 

It uses references to bind nodes together, thus the overhead of memory storage, and the randomness (usually insert order) in the array of nodes.

The random memory locations of the node data is precisely what this algorithm aims to eliminate, as well as reducing memory overhead. Walk operations only require very short 32 bit integer math functions to provide the location of nodes with various relations, mainly parent, child, and a lateral direction, that treats the tree as though it was a sparse sorted list (sparse because some elements will be empty, usually).

I was hoping you had put me onto something that resembled what I am doing but no. Sparse versus Dense is the conceptual polarity I am working from here, not Partly Empty versus Complete. The powers of two formulas I use allow me to derive relations between members of a 1 dimensional array that map to a complete binary tree, but it's not a complete binary tree because it has empty nodes, and these empty nodes are very important because they mark the momentary boundaries and constraints required for search, insert and delete (especially delete, where a subtree can be severed and become unreachable).

 

> Unlike simple, stupid newbie mistakes, this is intentional. I am writing this
> algorithm because it, by its architecture, reduces random access of memory,
> and in this, it gains a benefit of reduced cache misses in the CPU and thus
> will have, potentially, a serious performance advantage compared to any
> search-and-sort algorithm whether it be hashtables or vector reference based
> binary search trees.

You keep on making references to the efficiency of this algorithm, but
I don't see any benchmarks or algorithm analysis that supports your
viewpoint here.

Benchmarks would require a completed algorithm. I will absolutely be profiling it once it's done, in order to work out the comparative processing loads for each type of operation. I have a vague concept of the heuristics for optimisation operations, but I had been putting off filling these parts in because I still hadn't achieved the data type abstraction at that point. 

The general rules for these tree rotation operations, in the BAST idiom, are simple, and mostly depend on the lateral walk operations,  but need to know also when the directions are up and down in each sideways step. The root can be fairly easily displaced sideways from one side to the other to maintain left/right balance, and this operation can precede the insert and delete operations, but in some cases it may be better to stepwise displace sideways from an insert on an overweight side, but if this was always how it was done it would become a very expensive operation on a large tree.

At this point the *potential* for a performance benefit is fairly clear, but it can't be said with certainty how much and in what conditions there is a benefit, and indeed, when there might be a disadvantage. A lot of this hinges on the tree balancing operations. It is almost unquestionably true, however, that for searches, this structure will reduce memory access latency, and if it were implemented on a spinning disk, the benefit would be extraordinary (and this is something that I might be able to learn some things about with the trees used in filesystems). 

(which I am going to now, on that note, go and do a little bit of reading).

Thanks for your discussion about this... it's implicitly complimentary to have my ruminations actually read and considered.

[Louki Sumirniy]

I just dug into the data structure spec for Btrfs, figuring it would have trees in it, and no, they are not implemented in the way I am working here either.

Yes, it may well be that I am on a wild goose chase with this, but hey, I've learned an awful lot of cool stuff now that will serve me well later anyway, regardless of whether this succeeds or fails when the rubber hits the road.

[Louki Sumirniy]

Looking more into "Complete" binary trees, it's somewhat relevant in that this structure probably should be pushed upwards and the upper reaches of the tree made as complete as possible. Given a random source of data to fill the tree with, the odds are that the middle values will dominate due to normal/gaussian distribution, the only optimisation problem there has to do with when laterally adjacent nodes are numerically adjacent, yet they are towards the top of the tree. These nodes block any further inserts below them and need to be pushed apart, I call this 'declumping', it's one of the elements of the heuristics I have developed so far.

[roger peppe]

On 24 April 2018 at 09:58, Louki Sumirniy

<louki.sumir...@gmail.com> wrote:
>
>
> On Tuesday, 24 April 2018 11:15:34 UTC+3, rog wrote:
>>
>> On 23 April 2018 at 19:58, Louki Sumirniy
>> <louki.sumir...@gmail.com> wrote:
>
>
>>
>> > I set many of those identifiers to export because I wanted to keep
>> > separate
>> > derived libraries that replaced the storage types embedded into the main
>> > library. These limitations would not exist were the 'back store' over
>> > the
>> > wire or on disk. They only exist for the storage that is most accessible
>> > to
>> > the program, the main memory.
>>
>> I don't understand this. If you're replacing the underlying storage
>> types, why would you need to export details of an algorithm that the
>> storage types shouldn't need to have anything to do with?
>
>
> Because if they can't be accessed outside of the scope of the file I am
> forced to add the alternative data types within the same file.

I can't parse this sentence. There's nothing stopping you from having
alternative storage implementations outside the package AFAICS. Also,
file scope isn't really a thing in Go (*).

> This is a
> massive loss of flexibility (and means an importing application cannot
> implement its own variant).

In my experience, allowing external code to "implement its own
variant" by exporting all the component pieces of an algorithm and
allowing it to arbitrarily vary them is a recipe for cryptic APIs and
broken invariants. This is a hallmark of class-hierarchy-based OOP,
which is a style that Go specifically avoids. I'd suggest exposing as
few moving parts as possible. If someone wants to change the
algorithm, let them fork the code.

>> > This idea that I should be hiding all the functions smells like OOP to
>> > me.
>>
>> This isn't OOP - it's just good code hygiene. By hiding implementation
>> details, you make the public interface clear and you prevent clients
>> from relying on internal implementation details that you might want to
>> change.
>
>
> How do I override the functions to implement the data abstraction if the
> overridden functions are not exported?

Don't do that. You've got two principal abstractions here - the
underlying storage (more-or-less a slice) and the algorithm itself.
It's important to be able to change the storage implementation, but
the algorithm itself does not need to be able to be overridden. I
think you're still thinking as if you're in a subclass-based language.

>> Private functions are not "security by obscurity". Private functions
>> aren't "obscure" (you can see them in the source perfectly well) but
>> they are "secure" because you cannot access them.
>
>
> This is nonsense because all I have to do is fork and expose and what
> exactly is the nature of the danger of me knowing the internals?

There is no danger in *you* knowing the internals, but there is danger
in *external code* depending on the internals.

>> I think you overestimate the novelty of your algorithm. It sounds to
>> me like it bears significant resemblance to a "complete binary tree"
>> (see https://xlinux.nist.gov/dads/HTML/completeBinaryTree.html).
>
>
> A complete binary tree does not have a concept of empty nodes.

It must do, because a complete binary tree can be implemented by an
array and does not have to have exactly 2^n nodes, so by implication
some of the nodes in the array may be empty.

> It uses references to bind nodes together, thus the overhead of memory
> storage, and the randomness (usually insert order) in the array of nodes.

If by "references", you mean "pointers", that's not true. As the link
I included says:

It can be efficiently implemented as an array, where a node at
index i has children at indexes 2i and 2i+1 and a parent at index i/2

That sounds very like what you're doing.

> The random memory locations of the node data is precisely what this
> algorithm aims to eliminate, as well as reducing memory overhead.

Your algorithm can waste up to half the overall storage space. I don't
see how that's "reducing memory overhead" in general.

> Benchmarks would require a completed algorithm. I will absolutely be
> profiling it once it's done, in order to work out the comparative processing
> loads for each type of operation. I have a vague concept of the heuristics
> for optimisation operations, but I had been putting off filling these parts
> in because I still hadn't achieved the data type abstraction at that point.

I'd suggest starting with the basic algorithm without any abstraction
(just hard-code in the type you want to store), then benchmark/tweak
the algorithm, and only then try to make it general.

> Thanks for your discussion about this... it's implicitly complimentary to
> have my ruminations actually read and considered.

Your ruminations are verbose enough that I suspect I won't be reading
them much more in the future, I'm afraid, but I hope my thoughts have
been useful to you.

rog.

(*) technically, package identifiers are in file scope, but I'm pretty
sure that's not what you were referring to.

[Louki Sumirniy]

I'll just be brief this time and hit the points quickly:

Yes, technically it is a Complete Binary Tree but you won't find a Complete Implementation of one anywhere, I have looked, and there isn't. The concept has been rejected without being tested by anyone who has considered it at least what I can find.

Those relational functions you mentioned are not correct for a tree with the array index 0 being the root, this is them here:

Parent:

    c.Index = c.Index>>1 - (c.Index+1)%2

Left Child:

    c.Index = c.Index<<1 ^ 1

Right Child:

    c.Index = c.Index<<1 + 2

I have used bitwise operators because it is always powers of two, and thus will be faster on a processor with bitshift and no worse than using *2 without. I used an XOR on left because the shift is left and thus the LSB can be flipped without computation to add one. The right one adds two, this is related to using 0 as the root also.

The parent function is the one that got me the most excited when I came up with it - it avoids the use of comparison/branch functions by taking advantage of the property of the tree rooted at 0, that every left child is odd and every right is even (that's what the IsOdd function returns - and computes it with &1, and is used in my Left and Right walk functions that 'flatten' the tree and walk it like it's a sorted list). By adding one to the index you flip its' odd/even status, gives you a 1 if it then becomes odd. This effectively is a 'move inwards' operation. It saves on comparison and branching and I know on 32 bit integers bit shift, addition and modulus are very fast. (and the code is very short in the cache)

By rooting the tree at array index 0 it becomes possible to pick any given index and know if it's a left or right child by whether it's odd or even, and the special case of zero, which is neither (yes, I know it's referred to as even but it's not really a number, according to number theory), tells you also you can't move upwards.

Compared to a potential and mostly filled tree of 30 rows, the amount of space taken up by the code is quite small, with the separation of functions for tree and data type, there is no wasted space repeating functionality that can be abstracted. Plus, for up to around 20 rows of tree, the array will fit mostly within a cpu cache, and since operations take place on one side and the other, and mainly affect small segments of the subtree, each subsequent row does not have to be fully loaded into the cache for most operations.

Technically my approach is more like a functional programming approach to the problem, as I am passing pointers to functions in order to implement the data specific elements, only the interface for the array store is OOP style (and it DOES have to be encapsulated in a struct because Go slices do not work with interfaces).

As to exposing things, in fact an external payload data type library can decide exactly what it will expose. I am only writing a base implementation with uint32 because to test it I have to fill the data with *something* and quite likely 32 bit hashes will be actually used in my intended application for this library, as the heads and tails from 64bit hashes.

[roger peppe]

On 24 April 2018 at 12:59, Louki Sumirniy

<louki.sumir...@gmail.com> wrote:
> I'll just be brief this time and hit the points quickly:
>
> Yes, technically it is a Complete Binary Tree but you won't find a Complete
> Implementation of one anywhere, I have looked, and there isn't. The concept
> has been rejected without being tested by anyone who has considered it at
> least what I can find.

Actually, I think it's probably a "full binary tree" you're thinking
of rather than a complete binary tree, although I can't tell until you
implement some of the insert or search operations. FYI a complete
implementation of a complete binary tree can be found in the Go
standard library as part of the heap implementation: see
https://golang.org/pkg/container/heap so it's hard to say the concept
has been rejected by everyone. It's the standard algorithm for a
binary heap.

> Technically my approach is more like a functional programming approach to
> the problem, as I am passing pointers to functions in order to implement the
> data specific elements, only the interface for the array store is OOP style
> (and it DOES have to be encapsulated in a struct because Go slices do not
> work with interfaces).

I'm sorry, there really is nothing functional-programming-like about
your implementation.
Use of function values does not imply a functional programming style.

> As to exposing things, in fact an external payload data type library can
> decide exactly what it will expose. I am only writing a base implementation
> with uint32 because to test it I have to fill the data with *something* and
> quite likely 32 bit hashes will be actually used in my intended application
> for this library, as the heads and tails from 64bit hashes.

If you're using 32 or 64 bit hashes, you really should not assume
you're cannot get zero-valued hashes.

[Louki Sumirniy]

I spent a bit of time thinking about all the indirections in my code and decided I'm going hybrid functional/procedural on this, and minimising the visible overhead that the OOP constructs are clearly creating. One nice thing about Go's hostile attitude towards OOP is that when you find the way to do it, you realise 'oh, that's why go doesn't like it'.

soo, </thread> for me :) unsubscribing and not ruminating any further (*sigh of relief in the peanut gallery*) :D

[Louki Sumirniy]

Reading through the wikipedia description of a heap, and especially a binary heap... it's a heap. But that's not a sexy name! Technically it's not a heap because it sorts left to right, heaps sort bottom to top.

I am stripping down my code and directly declaring the struct variables as function types, and I will be removing the method-interface completely, as I don't need it. I will be able to then isolate the external interface functions and 'hide' the internals while being able to easily link the scope of functions to the structure.

If I really need a secondary value to flag empty or not, then the memory efficient way would be to have a bit-indexed flag for this property, so for every 32 bits of data one bit of flag and keep this in an orthogonal entry in the structure. You are correct, though the odds are small, probably 1/2^40 for 32 bit hashes making zeros, that kinda works out to 2^32/2^40 frequency of all zeroes and I think that amounts to 0.390625% being zero. That would have been a problem! So for 30 rows of 32 bits I will need 2^30 array elements, 2^30/8 bytes to store the empty/fill. I can't think of a more space efficient way to store this property. About 134Mb would be required for this, based on 30 rows. It can, however, be extended at the same time as the tree so its size will keep this proportion linear to the size of the tree array, it's not a big overhead compared to the 4Gb the 30 row store will use.

If it seems like this is excessive numbers, this stores 1/4 of the total magnitude of possible values of 32 bit hashes, or half hashes. In the application I have in mind, probably most of the time trees won't grow to more than about 15 rows anyway, which is not that much, before the required pattern is found in a hashchain, at least until the number of miners on the network gets really big. I am writing a Proof of Work algorithm and I was aiming for something that would scale down to short time periods at low difficulty.

This tree store would satisfy that by allowing solutions to pop out at a particular sequence in a hash chain derived from a nonce, and so workers would be able to find solutions in a much more temporally distributed manner than occurs with Cuckoo Cycle and Equihash, which both use array sorts to do their searches. Hence the reason for using this type of structure. And the reason for wanting to use a compact underlying storage is precisely about maximising the caching efficiency in the CPU, because I want to write a solver that can't be sped up significantly with a faster memory bus and/or memory cell retrieval latency (and further, retrieval latency in memory cells still has a minor but significant amount of extra latency for random access, thus wanting to reduce the memory footprint, and increase linearity). It makes absolutely no sense to use a reference based binary tree for values that are as small as the references themselves, as this implies automatically a 4x size of memory required.

ok. again, big thanks for your help with this, I really will stop ruminating, I promise!

[matthe...@gmail.com]

I'd suggest starting with the basic algorithm without any abstraction 
(just hard-code in the type you want to store), then benchmark/tweak 
the algorithm, and only then try to make it general. 

This is my conclusion too. Abstracting the code is a lot of churn if we’re not sure performance without abstraction works. We’ll be able to help on the Go front better with a foundation.

Matt

[Louki Sumirniy]

https://stackoverflow.com/questions/6531543/efficient-implementation-of-binary-heaps

Pretty much what I'm working on here is this, except with left to right sort instead of vertical. I think this guy's work will help me iron out the performance issues.

Another thing, that is more on topic more specifically, is that collections of interface methods introduce a significant overhead, compared to simply passing the pointer to the structure as a parameter. I am thinking that maybe a way to hide this parameter passing is by using closures, which bind in the namespace from a hypothetical initialiser function, without actually having to specify the pointer passing across. The structure is created and allocated by the initialising function (constructor, if you like) and because all of the functions are declared within the namespace as closures, the compiler implicitly passes the pointer to the struct without having to specify it.

I don't know exactly what FP paradigm says about structures and collections of functions exactly, as prima facie it looks like OOP. But closures are a uniquely FP mechanism, and really they are just a way to merge namespaces, and by doing this we don't have to pass the pointer to the function explicitly, as it is already accessible.

At least this is the tack I'm taking for today's outing into attempting to create a binary search tree with cache data locality. To some extent the benefits of this have been demonstrated with some other, relatively new algorithms like the one linked to above, and many of the same principles will apply. Index starting at shortens the walk functions significantly. Also, there is a question about the nil value for nodes. As someone pointed out, a non-trivial amount of hash results will be zero. Unless I'm mistaken, this also means that at that point, a hashchain would repeat, as this common originating value necessarily produces a common output. So in fact, I can use the zero sentinel or nil node payload, because we can consider the hashchain terminated if it does make a zero, and there is no point going any further as the remainder of elements of such a hashchain will be the exact same pattern as starting from a zero nonce.

[roger peppe]

On 25 April 2018 at 08:05, Louki Sumirniy

<louki.sumir...@gmail.com> wrote:
> https://stackoverflow.com/questions/6531543/efficient-implementation-of-binary-heaps
>
> Pretty much what I'm working on here is this, except with left to right sort
> instead of vertical. I think this guy's work will help me iron out the
> performance issues.

You do know that heaps aren't a great data structure for searching, right?

> Another thing, that is more on topic more specifically, is that collections
> of interface methods introduce a significant overhead, compared to simply
> passing the pointer to the structure as a parameter. I am thinking that
> maybe a way to hide this parameter passing is by using closures, which bind
> in the namespace from a hypothetical initialiser function, without actually
> having to specify the pointer passing across. The structure is created and
> allocated by the initialising function (constructor, if you like) and
> because all of the functions are declared within the namespace as closures,
> the compiler implicitly passes the pointer to the struct without having to
> specify it.

You don't need to do this. You're still thinking in traditional OO
terms. I'd suggest trying to think in a more Go like way instead. FWIW
I tried to point you in a more sensible direction with this code:
https://play.golang.org/p/wv0T8T8Ynns

> I don't know exactly what FP paradigm says about structures and collections
> of functions exactly, as prima facie it looks like OOP. But closures are a
> uniquely FP mechanism, and really they are just a way to merge namespaces,
> and by doing this we don't have to pass the pointer to the function
> explicitly, as it is already accessible.

What gives you the idea that closures are a uniquely FP mechanism?

rog.

[Louki Sumirniy]

I think that it's not necessarily non-idiomatic to use closures instead of interfaces in Go, it's more that Go has had interfaces longer than it's had closures, and so more code has been written this way.

In Angular 2+ you have the option of embedding HTML, CSS and TS code inside one file, or instead having 4, with the main file importing the other three. I don't like this for several reasons, but mainly because it makes a more complex interlinking between them, and I think even you can say that if your application is big enough, all this extra import work will also cost a lot of time, though in Go of course that time is not so big in the first place due to how efficient its compiler is.

The way I see it is that closures and interfaces are two ways to do exactly the same thing, binding namespaces together. One requires more accessory declarations and lines of code, not a huge extra overhead, but then for exported stuff - well, this is the one upside of it but I don't think it is that great, gofmt wants to see header comments on every exported function. Which is a nice idea, in theory, but in my opinion if you need comments your naming scheme sucks.

That's also why I created distinct comparators with meaningful names instead of creating named return values. b.IsEqual(data, cursor) compared to b.Compare(data, cursor) == EQUAL is not just a lot longer, but harder to read. I think technically it may also consume more code cache space to implement this extra operation, though on the other side, there is a small extra overhead for having three instead of 1. The compare function has to run three cases, most concisely expressed as 

    switch{

        case b.Store(c.index)>d: 

            return GREATER; 

        case b.Store(c.index)<d: 

            return LESSER

    }

    return EQUAL 

If my function only needs to know if it's equal (for example a search tree walk), it's just done two comparison/branch operations for absolutely no reason, and if I switch the order to benefit search, I raise the cost of determining which direction to step next after no match on a node.

I worked for a little while on the C++ server application for the Steem network node, and I was intending to remove a whole swathe of code relating to protocol changes at various hard forks. The number of times I ran across poorly ordered if/then (not even using switch!) that would perform unnecessary comparisons in more cases than not, to me it explained the ballooning amount of time that was required to play the blockchain into a database shared file. Literally, over a week, at that point, almost 9 months ago, and last I heard 270Gb of memory is required because this playback takes a stupid amount of time (effectively, eternity) unless the shared file is stored in a ramdisk.

So, just to be clear, I am not using OOPish techniques because I am a believer, and I don't think that convention should dictate effective programming either. Closures are a more compact notation than interfaces, and for me this is equally important as writing code that does not waste cycles doing things for the sake of some arbitrary model that does not greatly improve maintainability and readability at the cost of overhead that will stack up the more this approach is used.

Heaps have certainly got some disadvantages compared to bucket sorts and reference based trees but the one thing they have is data locality. Data locality can be a huge advantage because of CPU cache misses being avoided. Cache memory on my i5 CPU is 14Gb/s write speed. The DDR4-2400 memory in my system writes at 4Gb/s. This is linear writing, in the case of the main memory, so not only does conventional binary tree architecture cause a very high bandwidth load on the main memory, it also seeks the data randomly which adds even more delays due to the linearity of the memory cells.

To illustrate my point, here is a couple of articles I found relating to this and how data locality has brought massive performance benefits in reverse proxy servers: https://queue.acm.org/detail.cfm?id=1814327 and I found this story from this stackexchange topic: https://stackoverflow.com/questions/6531543/efficient-implementation-of-binary-heaps

The benefit of exploiting the properties of cpu and memory caching yielded a net boost of nearly 10x. I can't see how, at bare minimum, based on the ratios of cache and memory write speed on my system, I won't see close to or around 3x improvement compared to reference based binary trees, and potentially a similar kind of improvement compared to bucket sorting (which is how Cuckoo Cycle searches for cycles in hashchains). 

I don't know anything about what actual result it will have, but I am building it anyway, and I will use closures because I personally prefer the notation.

[Louki Sumirniy]

As you look deeper into the link discussing the B-heap you can see that actually I am pretty much exactly following the same general structure in my algorithm. The structure will align neatly with page boundaries and that means less page faults and reduced pressure on the virtual memory mapping system that means actually the tree can go a lot larger while cutting down delays on retrieving data. I intuitively understood this in my own visual model and this picture in particular is exactly how I visualised the data storage map:

 (this necessarily also requires a 1-root)

but then the B-heap reduces the fragmentation of the memory through the page even further:

Soooo, I probably will be considering revising the mapping to correspond to this as I can see why it would reduce paging during both searches and 'bubbling up' (in my case, bunching up, as in inwards) required to maintain a high fill ratio.

[Bakul Shah]

Roger is right. A heap can be a good structure for a priority queue but not for search. That is because it is partially ordered and siblings are not in any sorted order. In any case heaps are typically implemented with a vector. Go already has a pkg for it. go doc heap.

Seems like you’re doing something with blockchains. If you can clearly describe the precise problem you’re trying to solve (or point to an existing description), without getting into implementation issues, we may be able to help. Right now it is hard to reverse engineer the problem from your code and messages to this list.

--

[roger peppe]

On 25 April 2018 at 10:08, Louki Sumirniy

<louki.sumir...@gmail.com> wrote:
> I think that it's not necessarily non-idiomatic to use closures instead of
> interfaces in Go, it's more that Go has had interfaces longer than it's had
> closures, and so more code has been written this way.

Sorry, that's just not true. Go had both interfaces and closures on
the first day
of its public release.

[roger peppe]

On 25 April 2018 at 10:24, Louki Sumirniy

<louki.sumir...@gmail.com> wrote:
> As you look deeper into the link discussing the B-heap you can see that actually I am pretty much exactly following the same general structure in my algorithm. The structure will align neatly with page boundaries and that means less page faults and reduced pressure on the virtual memory mapping system that means actually the tree can go a lot larger while cutting down delays on retrieving data. I intuitively understood this in my own visual model and this picture in particular is exactly how I visualised the data storage map:

To expand slightly on why this data structure isn't good for
searching, imagine you're searching for the number 40 in either of
those pictured data structures. When you're looking at the root, you
have to make a decision whether to move to the left or the right
child, but you can only see 2 and 3. How do you decide that you need
to go left? Now imagine you're searching for 31 - how do you decide
that the correct direction is right?

[matthe...@gmail.com]

I worked for a little while on the C++ server application for the Steem network node, and I was intending to remove a whole swathe of code relating to protocol changes at various hard forks. The number of times I ran across poorly ordered if/then (not even using switch!) that would perform unnecessary comparisons in more cases than not, to me it explained the ballooning amount of time that was required to play the blockchain into a database shared file. 

What I’ve been saying is you should look at a performance measure to prove a hypothesis like this one. Removing that code may or may not work.

I think you’ve mixed optimizing the algorithm and code, and we have to look at one at a time to effectively reach your goal. A program that measures progress toward the goal (performance) is a foundation I think we can more seriously start from for the code part. Can you share something like this with us?

Matt

[Louki Sumirniy]

Always the elements are inserted according to greater than and less than. equal can't happen. The first value inserted will be the root to begin with, but if the tree gets heavy on one side, you rotate the root to rebalance. from any given node, you know that you will find the element you are looking for according to the node you are at, and its greater or less than test. You can know this is always going to be true because that's how the inserts will populate the tree, and the 'completeness' constraint enforces a requirement for the 'bunching up' of data. So long as there is space between two nodes, they can be as high up in the tree as the distance between them, each row downwards allows a power of two sequence of increasing numbers. The 'completeness' constraint is extended by not allowing orphans, every child has a parent, until you get to the root, so vice versa, you know that you will find every element in the tree by walking downwards and going left or right depending on greater than and less than, this is the comparability constraint. You should be able to see that a number of architectural features in this data storage system imply heuristics for optimisation.

Just to update, reading about B-heaps and how it structures storage, I realised that I need to think of the tree in terms of 4kb blocks (well, for most platforms) as this is the amount of memory that will be accessed in one operation. However many rows a payload size fits into 4kb is the size of each subtree. So for 32 bit values, I have one page at the top, and then 1024 pages that are the left and right pairs of the 512 elements at the bottom of the first page, and, of course, this repeats again. This changes how I have to implement the walk functions, as when it overflows past 512, I know I have moved to the second page-row.

So... I have to kinda go back to the drawing board a little on the structuring of the algorithm since it is working on 4kb page sizes. I may have to switch up the design so that the pages are the primary indices of the first dimension, and then the pages themselves, the subtrees, can be allocated as fixed length arrays, which also simplifies how Go will deal with them. Further, instead of allocating whole rows at a time, only those rows that have been breached require allocation of a new page for a subtree. In this respect, then the question about search cost becomes a little different, since we use 4k pages, and we know walking them goes on inside 14Gb/s SRAM cache, performance optimisation by tree balancing has a somewhat different character than the Binary Heap linear mapping.

Why do I seem so confident about the performance of this, potentially? Look up B-heaps and Varnish reverse proxy. It is designed at the low level with the same basic concept in mind, using B-heaps - structure the heap segments according to memory pages. If you are familiar with filesystems, you may know about block alignment. It's not quite so important for spinning disks but for flash and S/DRAM, memory is only ever handled on the hardware level in these block sizes. Disks usually use 512 byte blocks in the FS level and generally most disks have 512 byte blocks, some have 1k, 2k, 4k or 8k. Most current generation FS's use 4k blocks as the default size, for the reason it is a 1:1 mapping with memory pages.

The difference with what I am designing is that it does not order vertically, it orders horizontally. It's basically fractal, each subtree has the same number of potential subtrees below it.

Any code that keeps data aligned to memory page and disk page sizes is automatically significantly faster, because misalignment automatically doubles the amount of memory that has to be accessed to satisfy a request. This is why Binary Heaps are way slower than B-heaps.

Anyway, because many of my assumptions based on my conceptual model have changed, and big thanks to you guys, I have to rework the design to account for this. Thanks :p

[matthe...@gmail.com]

Any code that keeps data aligned to memory page and disk page sizes is automatically significantly faster, because misalignment automatically doubles the amount of memory that has to be accessed to satisfy a request. This is why Binary Heaps are way slower than B-heaps.

My opinion is without measurement you will miss necessary knowledge found between assumptions. The package testing benchmark has non-obvious features for repeatable data: https://dave.cheney.net/2013/06/30/how-to-write-benchmarks-in-go

I see you have logic tests (https://github.com/calibrae-project/bast/blob/master/pkg/bast/bast_test.go), and benchmarks are another step.

Matt