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.
On Monday, 23 April 2018 20:06:08 UTC+3, rog wrote:
>
> On 22 April 2018 at 23:20, Louki Sumirniy
> <louki.sumir...@gmail.com <javascript:>> wrote:
> > 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.
>
> 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.
>
--
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+unsubscr...@googlegroups.com.
For more options, visit https://groups.google.com/d/optout.
