More rants of a dead man

It’s hard to imagine there is a data structure that hasn’t been invented yet. wikipedia around and you’ll find dozens of oddly named trees and graphs and heaps and so on. All the great ones were invented or discovered (however you see it) in the 60s, and here we are 50-60 years later, you think that’d all be done by now.

So here, on 9/5/2020 I offer up the Stree.

It’s rather simple which is why I’m guessing somebody’s already done it at least in some form.

It combines a binary search tree with J. W. J. Williams’ binary heap.

The binary heap is a really neat data structure because it is tightly packed (‘complete binary tree’) and sorts pretty quickly, and you can find the child or parent of a node with simple math, if it is stored in a linear array of memory. Genius and brilliant at the same time.

As with all old things people have improved on it (Floyd came up with a faster build-the-initial-tree scheme) and I hope somebody can improve upon my idea, if in fact there isn’t one like it already.

I was looking for a tightly packed binary search tree and I couldn’t find one. So I thought about it for a bit, kinda wondering why it didn’t exist and came  up with this:

The binary heap makes the tightly packed tree by always only adding a new node at the end of the array of memory, and swapping nodes around until the tree is ‘correct’. In the case of the binary heap, correct is the parent key is greater than the child key. Doing a postorder  traversal of the tree will yield a sorted list (for a max heap tree).

The problem with post order traversal is that you can’t binary search it, or at least I can’t because the tree is sorta turned 90 degrees, and you can’t search sideways.

So how do we make it a binary search tree?

Kinda the same thing the binary heap does, but instead of swapping nodes on insert until the tree is max-heap correct, you swap nodes until it is binary search tree correct.

This is not as simple as making a max heap correct tree, but it’s not that much more complicated.

Since a binary heap is lopsided to favor bigger numbers as you go up the tree, you only have to go up once to find the final position of whatever number you are inserting.

A binary tree has one of its middle values at the top, so when inserting a new value into an stree, you have to swap values up to the top of the tree and then swap values back down (sometimes reswapping something you’ve already swapped) until you find the correct final resting place for the newly inserted value.

There are some other problems, and there are optimizations to be had, I haven’t worked out every single case yet, but I think it’s workable.

What happens, is like a binary heap, you insert by adding a new value at the next available space at the bottom/end leaf of the tree, or make a new row if the bottom row of the tree is full, and then start swapping nodes up until you get to the top. If you’ve found your final resting place (by comparing to the root node, based on what side you started on) you’re done, if not, you start working your way down the tree again until you’ve basically binary searched your way to where the new node is supposed to be.

It turns out that along the way, some of those swaps cause localized parts of the tree to become invalid, and then you have to go back and fix those too, but that only happens in the area of nodes that you’ve swapped, and you just keep track of things that need to be fixed as you’re doing all your initial swapping.

Worst case insert ends up being 2 * O(log n) plus a little bit more for some possible fixups.

I haven’t worked out node removal yet, but the concept is basically the same but backwards, you know which node you want to delete, and you know the spot in the tree that has to be freed up at the end, so you just have to swap up and down the tree until you get there.

I’m still working on this, but this is my basic idea, apparently data structures are not patentable, so I’m marking my stone in the sand here, as having come up with a usefully neat compact, binary search tree data structure.

Gotta go, my kid just woke up.

they say the two hardest things in software development is 1) naming things, 2) cache invalidation and 3) off by one bugs.

Amazon sells a product: amazon web services.

What is it?

It’s a bunch of software you can pay to use.

Google sells a product: google cloud platform.

What is it?

A bunch of software you can pay to use.

Microsoft sells a product: azure.

What is it?

A color.

I’ve been writing software for 40 years now, and I’ve seen a lot of things come and go. But I’ve noticed a trend towards the need to name things.

In the good old days, we used to write software. We wrote functions that did things, and we strung them together into programs.

Now we actually have a name for the fact that we need to name everything: “Patterns.”

A pattern isn’t an algorithm, it’s a word to explain that we categorize our algorithms.

So there’s the this pattern, and the that pattern, and because people can’t just say “well, that’s not a good idea.” they instead had to name that concept and call it an anti-pattern.

I think it’s all a bit silly and a waste of time given how hard it is to name things in the first place.

I don’t have too many good things to say about open source, but where there is something, I’m happy to admit it.

Lots of good comes from the open source movement. It keeps people off the streets for example.

ha ha.

A lot of great software and tools have come out of the open source effort, but an unbelievably massive amount of lousy software, broken systems and bar-lowering attitudes towards software quality also come from there. I’m not saying open source is completely to blame, but it certainly isn’t helping.

One of the popular arguments for open sourcing software is that it allows interested third parties to code review the software for bugs, security holes and other problems.

I have a lot of things to say about code reviews, but that’s for another book.

I hear the phrase “code review” and I think of all the programming jobs I’ve had where sometimes in a group setting people get to critique your software for various qualities.

My personal view is that code reviews should be for other team members to familiarize themselves with new code you’ve written, and to look for and find bugs. Possibly in trying to understand how new code is supposed to work, and asking questions, a team member might uncover a bug the programmer didn’t spot.

That to me, is the ideal.

But nothing like that actually happens. No two programmers will ever produce the same code to solve the same problem. Everybody has a different style, different handwriting, different experience. The argument over tabs vs spaces is such a common drama that to bring it up is merely to tell a joke so old everybody laughs simply because they know they get to have the tabs vs spaces fight again.

In a business setting, I have found people’s tendencies in code reviews tends to be more about ‘that’s not the way I’d do it’ than ‘tell me if you think this is a bug or not’. I’ve personally seen code reviews that contribute nothing more than “you should change this variable name to that.” I’m trying to imagine any customer that would be willing to pay more for a piece of software because the variable names were changed from one name to another. You could argue that maybe one variable name might be a little more descriptive than another, but not so much that the customer would be willing to pay that much more for it, since now it’s eaten up developer time and increased the cost of producing the product.

This endlessly frustrates me because time that could be spent testing and finding bugs it instead spend dwelling on variable names and source code formatting.

But this is where open source really shines.

It’s hard enough to get anybody to code review anything for free. So if there’s something really worth code reviewing, the reviewer is likely to spend their time looking for bugs or fixing a problem they found, not complaining about formatting or variable names.

This Is Genius. It’s a self solving problem.

Perhaps a lesson can be learned from this.

Software developers get paid to write software, perhaps they should have to volunteer their time to do code reviews.

Now will they volunteer their time? Probably not, but perhaps there is another way to incentivize people to do code reviews for no compensation. Like making it mandatory. Like suffering a penalty if you don’t. Or maybe there’s some backhanded complement kind of thing that can be done that would still drive the need to do code reviews, but only enough to do them the open source/find bugs way, not the corporate america/please-change-your-code-to-suit-my-tastes way. Oh and by the way, after you change code, you’ve invalidated all your testing, so you need to test it all over again, so if you did test anything before, that was a waste of time, because somebody asked you to change a variable name.

I’ll have to think about this some more, but this is clearly something the open source crowd does better than the paid business crowd.

I started writing a kernel module for linux recently. I’ve written small proof-of-concept kernel modules before, but nothing of any substance.

This time I wanted it to do something.

I have a friend who’s a linux kernel developer who’s been helping me out. You can’t really appreciate how different a beast it is to write software for the linux kernel, until you actually try it, or spend hours sitting with somebody who is.

I have not written or tried to write a kernel module for windows, but I have seen the source code for one and have code reviewed bits of it and had some of it explained to me by the author.

In some ways these two environments are similar and in some ways very different.

And it dawned on me, that deep down, the reason for this is, because the windows kernel was designed by people with experience in designing operating system kernels and linux is the culmination of thousands of scratched itches.

There is decent tooling for debugging the windows kernel, with an actual debugger, there’s actually two.

There is none for the linux kernel. It’s a big itch to scratch and nobody has yet been up to the task.

I’ve met some linux kernel developers and have heard them give talks. Despite all my experience and generally low opinion of software developers as a group, I for some reason thought that kernel development was a step up. You had to really have your shit together to endeavor to work on the linux kernel.

Turns out I was wrong, and you’ve got the same barrier to entry for writing software for the linux kernel as you do for writing any other kind of software: None.

No license or degree or certification is required. Any moron can write software for the linux kernel and if it scratches a sufficiently annoying itch, you have a chance of getting it accepted. To be fair, there is a mailing list where things like kernel patches are discussed. Actually there’s many mailing lists, because even the kernel developers who lack the sense to use a real messaging or ticketing system appear to acknowledge the fact that it is a good idea to split up discussions into groups.

The fact that it is 2019 and the linux kernel exists, despite being the sum of many dermatological challenges, organized by a messaging system dating from the 1970s, shows the true grit of humanity.

It is this same grit that allowed the space shuttle to come into existence.

It is pathetic to compare the two though.

I don’t usually foray into politics, but one thing struck me a few years ago as to why we appear to be sitting in a mess of politics that we haven’t had to deal with in a long time.

It’s only a theory, but its point seems to make sense to me.

The current generation of people in government are unique in the position that their generation has never seen real hardship.

They’ve not suffered a world war, nor have they been drafted to go to vietnam.

They’ve suffered no mass plague, or invasion. The economic recessions they’ve been alive for have largely been borne by their parents. The people who suffered in 2008-2009 maybe haven’t made it to the running-the-world age yet or are a small enough fraction that it doesn’t encompass the body of people who work in government.

But the basic idea is this: when there was a bigger enemy, or a bigger problem to deal with, you had less energy to spend on fighting your enemies to get your way, and maybe were more inclined to see the perspective of others, since you weren’t so dissimilar as you had common experiences (like a world war).

But now we have a whole generation who knows nothing but good times. No wars, or famines or economic depression. They’re so used to having the good times go their way, that they have less of a sense of co-operation and compromise. Why should they submit to anything being but the way they want, as that’s all they’ve known all their lives.

So you end up with factions of people who refuse to give in and let anything happen that isn’t the way they want it to be.

Just a thought.