Remosi's Rants

So, I’ve been doing some work on a network visualisation program called BSOD (Don’t ask), cleaning up code here, tweaking some stuff from there. Anyway I’ve got it running well under Linux. The final thing to do before a new version is released is compile it under windows.

Now, I’ve not seriously used Windows since about 1995. When Windows 95 was released my current computer more or less defined the minimum requirements, and through various events ended up using Linux. So this experience with programming under Windows was….. educational. I’m not unbiased in this; I’m used to doing things under Linux. I’ve been using Visual Studio 2005 under XP.

So, what was the experience like? Well, it wasn’t my favourite experience. Some things don’t work as I expect (Every time I try to use the middle click to paste I realise that no… I have to explicitly copy and paste it). Things are different so thats ok. What did bug me was Visual Studio. People explain to me how great Visual Studio is, but my experience was somewhat… different.

Solutions and Projects confused me. Does a solution hold projects, or do projects hold solutions? Why can’t I have multiple solutions open at once? One for building an external library and one for building the main program? Given two checkouts on the same machine, how can I tell what the path is to the file I have open in any obvious way? (I assume theres some way to find out).

Window’s weird ideas about files being open not being able to be touched is annoying. Especially when visual studio suggests that this is probably due to me using version control (wtf?).

Visual Studio recommends poor programming practises. Wizards produce bad code. One example is the skeleton code it produces when you generate a new console application:
int _tmain(int argc, _TCHAR* argv[])
This uses “_tmain”. Now in C/C++ identifiers that begin with an “_” are reserved for the standard library. Programs should avoid ever using identifiers that start with a “_” so that the standard library can use them for symbols that shouldn’t be leaked into the application. For instance <ctypes.h> on MacOS defines almost every single letter variable with a _ in front of it.

Visual studio doesn’t really try to be a C compiler. But it’s almost insulting to have the compiler tell me that my C program doesn’t conform to the ISO C++ specification. It makes me angry to have the compiler suggest changing portable functions (eg strdup()/snprintf()) to less portable versions. C99 was released 8 years ago, yet Microsoft don’t even mention <inttypes.h> / <stdint.h>. These headers are important for portability for applications that deal with integers of fixed length. Sure VS has it’s own non-portable ways of specifing these, but that just makes the oversight more annoying. The solution so far has been to implement our own <inttypes.h> and <stdint.h> for windows and ship them. Frustrating.

Linux doesn’t really have any one elegant way to describe where the library path, library name(s), and header files are for installed library. Two that spring to mind are pkgconfig, and *-config programs. However despite these rather obvious flaws, I don’t see any way to deal with this in Visual Studio eitherrather you have to add the library name(s), the header search paths, and the library search paths. And surprisingly library names aren’t selectable. Plan9’s solution is to have a “#pragma” that specifies the library to link against. Thus if you #include a header, you automatically end up linking against any library that they use.

Microsoft have said in the past that Linux is based on 30 year old technology. Under Linux things have been tried and tested. If they were found lacking then they have been replaced. Windows however appears to have managed to accumulated bizarre limitations directly inherited from the 16bit days. One example which bit me in the butt was that I can’t malloc() in my program, and then free() it in a library. Why? Because in the 16bit world malloc() allocates out of a pool of memory per DLL and a seperate one from the main program. But the limitations is annoying.

DirectX stuff appears to be complicated and rapidly changing. The code I’ve been playing with was written against DirectX 8. DirectX 8 however appears deprecated. (The documentation discusses it’s support for the new and upcoming “whistler” operating system!). However now it appears difficult to compile code against DirectX 8 now, newer SDK’s are geared more towards DirectX9 and DirectX10.

Many of the key combos I remember from my Turbo C++ days still work. The debugger works much the same way. I enjoyed playing with “Run to Cursor” again after all these years. I find using “bt full” from gdb to be much more useful than the annoying “watches”/”call stack”/”locals” interface, which appears to be more limited than I remember it being when I was using IDE’s in DOS.

I miss the flexibility I feel I lose moving to VS. VS seems to want things done in it’s preferred way. Sure you can override it, but you’re swimming against the current. I miss regular expressions, grep, and sed. For example “Find all references” doesn’t show any context, how do I know which one is the one I want? Why can’t I compare two files to see how they differ like I can with diff(1)?

I feel like I’m in Beijing and I don’t speak the language.

It occured to me how much knowledge is being lost since I taught myself to program. Programmers today "know" some of the low level details of how a machine works in theory, but really, how much do they know?

When I started teaching myself to code it was on an IBM XT with DOS. Now, if you're somoene who's never really used DOS (or CP/M or…) except in "DOS Box"'s, then you really don't know what it means to run a non multitasking, non protected mode machine. DOS is not very much more than a way to load programs into memory and run them. It provides only very basic abstraction from the hardware, and most of it is extremely slow and limited. the DOS API's were generally only ever used to read/write files. DOS was essentially treated a filesystem driver.

The realmode x86 chips had a weird memory model called "segmentation". Each segment was 64k, and segments overlapped with each other offset by 16 bytes. So offset 0010 in segment 0000 was the same as offset 0000 in segment 0001. You'd write these addresses as segment:offset. Programmers would regularly directly access addresses in memory that they knew contained things. I can still remember a lot of interesting addresses off by heart.

• 0000:0000 was/is the interrupt vector table
• 0000:7c00 – the bootsector was loaded into memory
• A000:0000 – the VGA Framebuffer was located.
• B000:0000 – the monocrome textmode display was located
• B800:0000 – the colour textmode display
• C000:0000 – this was "Adaptor ROM", or where network cards (and other things) put their stuff
• F000:FA6E – this was the VGA ROM BIOS Font

You talked directly to the hardware. If you wanted to hook an IRQ, go for it, overwrite the address it would use in the interrupt vector table, and remember to acknowledge the interrupt when it came time to return.

I remember to change the VGA palette you write the pallete entry you want to change to io port 0×3c8, then write the red value to 0×3c9, green to 0×3c9, then blue to 0×3c9. They could be from 0 to 63.

In fact, I remember you could poll an IO port (I must admit I've forgotten which one, 0×3CA?) and see if a horizontal or vertical retrace was in effect. Depending on the screen mode there were only 16 or 256 or whatever palette entries. Most of the time this meant that you could only have 256 colours on the screen at once. If you modified the palette while the video card was drawing on the screen you'd get "Snow".

Snow was caused when the video card tried to read a value that the host CPU was in the process of modifying. It would normally read out 0xFF or some other weird value instead so you'd get "white" in random places across the screen causing what looked like "Snow".

But you had enough time to modify about 4 entries during the horizontal blanking time (on my hardware at least) before it started painting the line and therefore avoiding the snow. This meant you could use 256*4+242 colours on the screen at once (on a 256 scanline resolution). Often this was used to change just the background colour, usually in a nice smooth gradient. This was called coppering.

By investigating what the other video registers were used for people discovered lots about how video cards worked. Video cards were only allocated 64k of address space, so to fit higher resolutions or higher bit depths in they used "planes" (or banks) that you switched into the 64k address space, wrote your updates to it, and then flipped in the next plane. Lots of interesting tricks could be pulled using these techniques. A lot of video modes were "chained". A write to video memory would write the same value to all planes simultaniously. These modes were fast and easy to program for, but they were stuck at very low resolutions. But by programming some of these low resolution modes and turning off the "chained" bit in the video card you could effectively create your own unsupported, undocumented video modes. These modes were collectively called "Mode X".

Because the machines were so slow, you spent a lot of time working on optimising code. Often you'd end up rewriting tight loops in assembly code. Even then you'd look at how you could optimise your assembly code.

x86 instructions are of dynamic length. There minimum length is 1 byte. Their maximum length was something like 6 bytes. I suspect on a modern x86_64 machine it's probably closer to 12 bytes by now.

Your bus was 8 or 16bits wide, and you had to wait for bus transactions to complete, so you'd want to choose the shortest opcode you could. Also memory was at a premium, every byte saved was going to be useful somewhere else. xor ax, ax was better than mov ax,0×0000 because xor ax,ax is a 1 byte opcode, where as mov ax,0×0000 was 3 bytes.

Unlike the RISC machines you get taught on at universities where everything is nice and simple and elegant, and instructions take a fixed number of cycles, on x86 they can take different amounts of time. xor ax,ax might take one cycle. a multiply or a divide might take a few hundred cycles. A sin or cos might take a small iceage. So sometimes you wanted to use more opcodes because they were faster but the achieved the same result.
One popular VGA video mode was mode 0×13. ("mode thirteen"). It was 320×200x256. To code a putpixel you needed to do (A000:0000 + Y*320 + X). But that had a nasty multiplication in it. Remember how you were taught to do multiplication at primary school?

32
 *320
 ----
    0
+ 64
+96
-----
10240

Imagine doing this in binary:

0000 0000 0001 0000
          *0000 0001 0010 0000
           -------------------
           0000 0000 0000 0000
         0 0000 0000 0000 000
        00 0000 0000 0000 00
       000 0000 0000 0000 0
      0000 0000 0000 0000
    0 0000 0000 0010 000
   00 0000 0000 0000 00
  000 0000 0000 0000 0
 0000 0000 0001 0000
<snip>
 ----------------------------------

0000 0000 0001 0010 0000

The thing to note is where there is a zero in the second argument to '*', there is a line of all 0's in the working, and where there is a 1, the first number is copied entirely shifted left by the position of the bit. So to multiply by 320 you could instead do res=(y<<5)+(y<<8). This was faster, significantly so. I remember benchmarking it

Other quirks of the x86 architecture were things like you could do complex addressing modes like [bx+4*ax+3]. this was handy when you needed to find the address of a member of a structure in a array. There is an opcode called LEA. Load effective Address. This instruction takes an address as it's argument and loads that address (not the value at that address) into some other register. The fun thing was that LEA was a single cycle opcode (and quite short 1 or 2 bytes IIRC). This meant that you could do a shift by a power of two, and an addition in one opcode instead of two. And not only that it wouldn't use the ALU to do the arithmetic so another opcode could be busy using the ALU.

One of my greatest "hacks" was a program I wrote that used one of the "Mode X"'s I mentioned above to create a 256×256x256 video mode. Most monitors hated this mode as it was effectively square, and they were 4:3, but with some protesting they'd do it. I created a subdivision style "plasma". Then each vertical refresh I'd blit onto the screen a tunnel going off to infinity with this plasma textured onto it.

Originally I wrote this in Pascal (Turbo Pascal v7 for DOS was a brilliant language, compiler, and IDE). Except it was slow. Glacially slow. So I started rewriting chunks of it in assembler. But I soon ran into the problem that intel machines don't have many registers. So I stored all the registers in the code segment (writable code segments yay!), and then used all the registers (including the stack pointer — which is why I couldn't store them on the stack) as general purpose registers.

It still wasn't fast enough. One of the reasons for this was I only had a handful of segment registers. Now when you're addressing memory in x86 realmode, you give an offset into one of the segment registers (CS (code segment), DS (Data segment), ES (Extra Segment), SS (Stack Segment) and I needed to access 4 buffers (vga buffer, texture, and x/y data for my tunnel).

So, I did some research and found the opcodes for the new 386 instructions, and tried using them. But turbo pascal's internal assembler didn't know about these opcodes. Now when it comes to x86 assembler there are prefixes for changing some characteristic about the next opcode. for instance a "ES:" prefix would modify the address in the instruction to be relative to the ES (Extra segment) instead of the DS (Data segment). If you used 32bit registeres in real mode the assembler would automatically output a prefix saying to use 32bit values/registers instead of 16 bit ones for the next opcode. This assembler didn't know how to do that. So I would use "db 0×66 ; mov ax, sp" to make the instruction "mov eax, esp". But then I discovered that the 386 had introduced another couple of segment registers (gs/fs). howeve there was no prefix for them, I had to hand assemble and insert the raw hex values for them into my program.

So now I had a program that I had hand assembled to make run, and now it ran fast enough to be useful on my machine, and it looked sweet!

But around the time of the release of ID's game "Doom" all of this disappeared. Compilers didn't produce completely moronic code anymore, and processesors were fast enough that you could afford to waste a few cycles here or there. The program I'd painstakingly hand optimised above I showed to a friend. He wrote the entire thing in C and it ran fine on his pentium computer. (his version however didn't run at all reasonably on my 386).

Doom was written almost entirely in C, including the 3d raycaster. Only the dissolve between missions was written in assembler. Soon computers were coming with 3d accelerated video cards and everyone forgot how to write assembler, except for the fringe lunatics and people who write compilers.

You might think that this is progress. No more do people spend a week painstakingly hand assembling code to get things to run as fast as humanly possible. But, the skills I learnt over 10 years ago when I taught myself to program are still useful today. Knowing the layout of a bootsector means I can correctly identify a lot more problems people have with disk images. Knowing assembly language in far more detail than anyone thinks is necessary helps with debugging obscure problems in programs.

You tell people today about hand assembling programs to get them to run at speed and they just won't believe you. :)

there is a python module called ctypes. This module lets you make calls to various functions inside a dynamically linked library without having to explicitly write wrapper code for it.  But you must specify the complete type of the function you're calling before you call it, so that the ctypes library knows arguments to push onto the stack and what order etc.

This always seemed to be a silly restriction, in an strong, but dynamically typed language such as python having to forward declare things seems to defeat the entire purpose.  And besides, when you compile something, you can compile it with full debugging symbols, which has the full type information about everything in your program anyway.

So, you could write a program to parse the debugging symbols out of an .so, and generate a python module with all the various type definitions and functions exported from the library, and you could do all of this on the fly.

And thus, I wrote it.

foo.c

struct function2_return_t {
        int a;
        int b;
};

struct function2_return_t function2(int a)
{
        struct function2_return_t ret;
        ret.a=a;
        ret.b=a+1;

return ret;
}

And the example usage:

>>> import ct
>>> ct.load("foo.so")
>>> import foo
>>> ret=foo.function2(1)
>>> print ret
<ct.function2_return_t object at 0x2aefd8f12650>
>>> print ret.a
1
>>> print ret.b
2

It's all still very prototypeish, it doesn't deal with pointers or strings yet. As you can see it deals with structs (as if they were classes), and could fairly easily deal with arrays and pointers to structs (although once you get into pointers, you get into "who owns this memory", perhaps requiring a .free() method on classes).  Strings should also be fairly straight forward if you can figure out who actually owns the memory (should it be freed?).

At the moment I run and parse the output of readelf to get the debugging information, and I don't properly hook the "import" mechanism to make it all completely transparent, but as a prototype I thought it was pretty cool. 

So if I want to migrate a networking process, chances are it's going to migrated to a machine that nolonger has the IP address that it started with, which breaks all current TCP/IP connections.  Suck.

But with IPv6, we have an abundance of addresses (2⁶⁴ per subnet), so we could trivially aquire a new IPv6 Address per process.  Mobile IPv6 allows you to migrate the IP address along with the process.  The kernel could do the IPv6 allocation, and route all packets to that address to the userspace process, and make sure that any packet arriving from userspace has the right source address.

Since all the networking state is stored in a library in userspace, when you serialise/hibernate the process (and restore it again), all your networking state is immediately accessible and usable.  This also fits well with Van Jacobson's NetChannels allowing for perhaps some of the performance increases he has seen.

I read a presentation by Tim Sweeney, about programming language design.  He talks about how games developers use programming tools, and has some surprising results. I was quite impressed by this.

I had noticed some similar things sometime about 2000ish.  I noticed a big block comment in some code (ircu) explaining what all the variables were doing in a particularly hairy piece of code, and thought "I wish I the compiler could read these comments and make sure the program matched them".  About the same time Beep pointed out that I should be using "assert(3)".

Since then I've decided that assert(3)'s are far more powerful than comments.  They document what the code is expecting to both a programmer, and to the compiler.  They don't get out of date, because the minute they are wrong your program aborts with a (only slightly) useful error message.  A commented out assert() is a sure sign that somethings amiss in your code.

However the compiler doesn't make use of these hints.  It doesn't warn me that the assert()'s are conflicting (assert(x==0); assert(5/x>1).  It doesn't use assert()'s as an optimisation guide.  It doesn't propergate assert()'s back or forwards through code.  I can't set up class invarients.  I can't set up assertions as continous relationships between variables.
The compiler doesn't let me annotate types with meaningful information.  Almost every pointer passed to a function should be "not null", the compiler could statically check this.  Global/static variables/thread constructor arguments/any other cross thread datastructure should have a "protectedBy(Mutex)" attribute and the compiler should enforce this by raising a compile error if a thread isn't holding the correct lock when accessing this variable.  Some variables should have constrained ranges (>1, >0, 0..10, etc) It has been shown that compilers can achieve some near miracles with type checking.  Why can't we tell the compiler what we're actually trying to achieve? 

And besides, why are we even using integers for all this stuff?  why dont we have better concepts like foreach/map/reduce/foldl/foldr in our languages?  How come we have to code a for loop using integer indexes all the time with the number of bugs that introduces?  When we really need an integer, we either want a limited range type (there are between 28..31 days in a month, so why should the compiler allow any other value?), a "BigNum" integer with practically infinite precision, or a "high speed" integer for use in vector operations.

While I'm here, why on earth do we still have an array datatype?  We should have a "list" datatype, and if the compiler  deterimines the size of the list, and that the list isn't excessively sparse, or dynamic, it could implement it as an array.  If we only append to the end of the list and pop off the front, a singly linked list might be appropriate.  If we ask for it to be "sorted" then it could be stored as a tree.  If we use "insert" "delete" and "key exists" methods, then perhaps it should be implemented as a hash table.  If we use append/pop and ask for it to be sorted, maybe it should be stored as a priority queue.  These are all determinable statically at compile time, why do we as a programmer have to decide on whats going on?  Worse yet, in many languages, why do we still have to code these datastructures over and over again?

The compiler is our friend.  It's doing us a favour of releaving us from some of the (significant) burden of writing programs.  Why then do we keep secrets from it and in places down right lie to it.  We should involve it more in what our program is doing, let it join in and proof read our code for us.

Heres the problem:
You have two (or more) datasets that you want to return the intersection of, but they are only accessible over a slow link. You can’t upload the smaller set to the larger set and have that do the intersection, so what do you do?

Example:
You have a distributed search engine where each node holds a list of urls that contain one term. A search comes in for “Hello World”, and you want to return the results of the Intersection of the urls that contain “Hello”, and the urls that contain “World”.
My solution:
Both lists are sorted in some way (and both are sorted the same way).

1. NodeA sends NodeB it’s lowest numbered id.
2. NodeB sends NodeA it’s lowest numbered id that is greater than or equal to NodeA’s id, and greater than any item it has previously sent.
3. NodeA and NodeB repeat step 2 until there are no more ids.
4. NodeA and NodeB now both have the intersection of NodeA’s ids and NodeB’s ids (as they’ve both been sent an id that they have too).

This will take at most 2*n operations where n is the size of the intersection. [Edit: hrm? where did I come up with that from. It's obviously not!]
As an optimisation you could split the list up into “n” divisions, and send the lowest one in each division each time.

Why does C++ have the const keyword? How often has it saved you from bugs? How many times have you seen “passing T to func ignores const” and it’s been because func really modifies T, and not just that you forgot to put const on the function? How many times have you seen that warning because you just forgot to mark something const that should have been? So why is const there other than an bit of enforced documentation? If it’s just enforced documentation how about some other semi-enforced documentation that might be useful? nonnull would be a great one especially for return types. In/Out/InOut are commonly used bits of information for documentation generators, so they must be important. What about “pure” on a function (has no side effects, so it can be hoisted out of loops, etc?) How about “owned” or “owned” on pointers? maybe “heap” for pointers that will be later free(3)’d and therefore must be on the heap? Why was const important enough to get the reserved word status, and why did nothing else get it? Why aren’t there programs out there that look at your code and say “Hmm, you should put a const here, and here, and here, and here”, in fact, why isn’t the compiler just figuring out if things should be const by itself? In fact why doesn’t the compiler look at the symbols that are defined in a .cc file and generate a .h of all the exported symbols anyway with annotations that the compiler might find useful (pure, const, non null, heap, etc)?

Sigh, I might be bitter and twisted about being forced to stick const on everything for no better reason than it makes my code look pretty, but why oh why is it there?

A lot of people hate reading other peoples code. Especially code bases that are very old. And while I must admit that trying to modify someone elses code is a real pain, sometimes sitting back and reading old code is rather enlightening. You may be sitting there looking at a piece of code trying to figure out what crack the developer was on while they were writing it[1], but you have to remember every line of code is there for a reason. Every single one. The code that half implements some feature is there for a reason. The author obviously decided that it was important to write at some point and then changed their mind. The code which is no longer relevant speaks of a time when that code was relevant. Code that works around some long forgotten bug in some library or kernel, or some limitation of a long dead compiler speaks volumes about what problems people in the past had to face. Code that tries to shave an extra 1kbyte here, and an extra 1kbyte there talks about what hardware that the programmers had to deal with. Code that has massive optimisations performed by hand by the programmer speaks to a time when CPU resources were limited, and the compilers weren’t smart enough to discover the optimisation for themselves. Code that never had any effect is a brief insight into a programmers idea of what the program is doing (even though it’s wrong). Bugs speak about the competancy of the developers and usage patterns of the users. Variable names also show what the developer originally thought was going on when she choose the variable name, (but not necessarily what they realise it does today). Comments provide short sentances in the story of the life of the program. Even which license chosen by the program explains a lot about what the original developer(s) wanted from the program, and what they were hoping to happen to it.

So next time you’re looking at code, cursing and swearing, stop to think about the story of the program. At least it’s an interesting diversion.

[1]: Surprisingly enough, I have found code where the authors do claim to be smoking crack while writing it….