uni

data structures

A link i found by casually strolling through Hacker News in the train: http://mattwarren.org/2018/06/15/Tools-for-Exploring-.NET-Internals/

I liked https://github.com/SergeyTeplyakov/ObjectLayoutInspector in particular, because it shows you how inefficient your class/struct layout probably really is. Because padding is still an “issue” if you want to call it that. I learned this in the last semester in my computer architecture course: compilers don’t magically optimize your memory layout. I wish i would’ve learned that earlier, since it’s not something people tell you. If you’re using a struct consisting of a sole single byte data type and your allocated memory-block has a width of 8 byte, then only 1/8th of the actual block is used. The remaining 7 byte are padded when the “next” object has a width larger than the remaining space, e.g. the remainder is filled with zero-values. In our example with only one type shows the nature of this problem, but not the implications.

Let’s say you have a struct with some more types. The fitting type is always first-fit, not best-fit. This is obvious if you had a hand at stack smashing (you might actually want some information strictly after some other information.) – another neat example can be found on the english wikipedia page for data structure alignment. You will see that the “remaining bits” of a word will always be padded if the following type does not fit in the block. So you have a word-width of 4byte, and some objects that use (1,4,2) byte (remember: the order is immutable.) each of these objects are stored in a seperate block since they don’t fit in the same one. so the first and the third objects are padded, although they would’ve fit in the same block. Lets say those are simple structs:


type example struct {
var first *verySimpleType // 1 byte
var second *notSoSimpleType // 4 byte
var third *kindofSimpleType // 2 byte
}

This would compile into:


type example struct {
var first *verySimpleType // 1 byte
var padding[0] // 3 byte
var second *notSoSimpleType // 4 byte
var third *kindofSimpleType // 2 byte
var padding[1] // 2 byte
}

This could be easily improved by switching the second and the third variables:


type example struct {
var first *verySimpleType // 1 byte
var third *kindofSimpleType // 2 byte
var second *notSoSimpleType // 4 byte
}

This would compile into:


type example struct {
var first *verySimpleType // 1 byte
var third *kindofSimpleType // 2 byte
var padding[0] // 1 byte
var second *notSoSimpleType // 4 byte
}

Holy hell, we would save a whole 4byte block. You think that’s not much? Let’s say we’re using a lot of data, like five million objects – in memory. That would be five million blocks with a width of 4 byte. That’s a whooping ~19 MiB, with just one block won. Consider an optimization of about 20 blocks, suddenly we are talking about ~400 MiB of memory. And now let’s say we are using the XMM registers, where a word has a length of 16 byte – that’s 2 GiB of memory.

While this is all theoretical improvement many people will never have to consider, it is – for my liking – a good example for things we have to optimize manually. And we shouldn’t rely on compilers, linters and code conventions more than we need to know about how computers actually work. Because “just get more memory” is an argument that i don’t ever want to use.

uni

Let’s talk a bit about memory management

So after almost finishing my class on operating systems and memory management (at the easy and superficial stuff) i’ve always wondered how one can put all the theorems in a touchable context, and right after i went into the bathtub it hit me.

I’m not talking about memory management methods right now, just if you have no idea about it, think of all the methods you COULD use to fill an array or slice (talking golang now) with other arrays or slices.

The thought is rather easy, let’s say you have an empty slice with len(s) = 32 and you need to fill it with an amount of other slices that are filled with whatever, some random data. The first iteration of data would be pretty straight forward, just putting them at the first free position (concerning it doesn’t exceed the length of the array, in this case 32) – otherwise it should either be rejected or enqueued. Now the fun part begins when you delete random slices from within the slices (e.g., s[0..7] and s[11..14]) and then try to put new data in there.

Now if you’ve got two slices enqeued with len(q[0]) = 4 and len(q[1]) = 8. In case you just put the data in the first fitting (Hint: That’s a keyword) place, there’s no more room for q[1].

This is easily adaptable without even having to get on a lower level of memory management on the OS abstraction level. You can play with this idea – if you’ve got sample implementations of this “problem” (I wouldn’t call it problems, but make of it whatever you want), hit me up so i can link them here 🙂

UPDATE: I did some untested stuff in a go playground, you can play with it. https://play.golang.org/p/ei5QgXBh_7S

hackering

AlarmPi?

The last few nights seriously took my energy level to a new low. Maybe part of that problem is the fact that since I’ve build this depression I’ve been watching Twitch-Streams to sleep in. Bad, bad, baaaad idea. So now i want to get rid of that and instead listen to soothing music when i get to bed. Not that hard, but somehow i don’t want my phone to be responsible for that. And my laptop? Way too loud, too much energy drain, etc.

So what do we do?

Easy peasy, let’s build an AlarmPi – and now that we’re on it: Let’s use it as an alarm as well. And now that we’re on it: Let’s build a mobile App so we can change all the settings. So, in my terrible sleepless idea-digging I figured i need the following things:

  • A playlist with soothing music (YouTube?)
  • A playlist with music to wake up to (YouTube?)
  • The possibility to set volumes, etc.
  • A neat web interface
  • A randomizing-button so we don’t get up to the same shit
  • A mobile app to control the neat web interface
  • Alarm Clocks (more than one?)
  • If more than one alarm: different playlists for different occasions?
  • Maybe some timers on when to start the soothing music and when to stop?

Looks reasonable, eh? So the Raspberry Pi is sitting on my desk, now let me get a few appointments out of the way (math exams, hooray.) and we’re off to go.

I’m still wondering if Go is the right language for that or whether i want to try something new. Suggestions?