On 23 April 2018 at 19:58, Louki Sumirniy <louki.sumirniy.stal...@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. > 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> 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. -- 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.
