XML is a Dumb Format For Storing Data

originally wrote by Joel Spolsky

I'm not sure why XML got so sexy. It has its advantages; it's sure a good idea for data interchange or for all those little files you need to store settings. But for real work it just can't do what a solid, multiuser, relational database can do. The next time some uninformed analyst at Gartner or Giga or Forrester tells you "in the future, everything will be XML," ask them how to do "SELECT author FROM books" fast with XML. Hint: you can't. It has to be slow. XML is not the way to store a lot of data. Now tell me how to insert a new book at the beginning of the table without massive bitblts. Of course, I doubt if there is an analyst in one of those companies who would even understand that sentence, but that's life. Now lets look at the books table in XML.

<?xml blah blah>
<books>
    <book>
        <title>UI Design for Programmers</title>
        <author>Joel Spolsky</author>
    </book>
    <book>
        <title>The Chop Suey Club</title>
        <author>Bruce Weber</author>
    </book>
</books>

Quick question. What is the code to move to the next record?

Uh...

At this point a good programmer would say, well, let's parse the XML into a tree in memory so that we can operate on it reasonably quickly. The amount of work that has to be done here by the CPU to SELECT author FROM books will bore you absolutely to tears. As every compiler writer knows, lexing and parsing are the slowest part of compiling. Suffice it to say that it involves a lot of string stuff, which we discovered is slow, and a lot of memory allocation stuff, which we discovered is slow, as we lex, parse, and build an abstract syntax tree in memory. That assumes that you have enough memory to load the whole thing at once. With relational databases, the performance of moving from record to record is fixed and is, in fact, one CPU instruction. That's very much by design. And thanks to memory mapped files you only have to load the pages of disk that you are actually going to use. With XML, if you preparse, the performance of moving from record to record is fixed but there's a huge startup time, and if you don't preparse, the performance of moving from record to record varies based on the length of the record before it and is still hundreds of CPU instructions long.

What this means to me is that you can't use XML if you need performance and have lots of data. If you have a little bit of data, or if what you're doing doesn't have to be fast, XML is a fine format. And if you really want the best of both worlds, you have to come up with a way to store metadata next to your XML, something like Pascal strings' byte count, which give you hints about where things are in the file so that you don't have to parse and scan for them. But of course then you can't use text editors to edit the file because that messes up the metadata, so it's not really XML anymore.

------
By the way, when I published this digest from Joel, I have no idea how to put the HTML code in my blog contents. Here is the solution, and the full table of escape characters are here.

some advices about low-level programming

see also <Back to Basic>
reference <Advice for Computer Science College Students>


Learn how to write

The difference between a tolerable programmer and a great programmer is not how many programming languages they know, and it's not whether they prefer Python or Java. It's whether they can communicate their ideas. By persuading other people, they get leverage. By writing clear comments and technical specs, they let other programmers understand their code, which means other programmers can use and work with their code instead of rewriting it. Absent this, their code is worthless. By writing clear technical documentation for end users, they allow people to figure out what their code is supposed to do, which is the only way those users can see the value in their code. There's a lot of wonderful, useful code buried on sourceforge somewhere that nobody uses because it was created by programmers who don't write very well (or don't write at all), and so nobody knows what they've done and their brilliant code languishes.

If you can write, wherever you get hired, you'll soon find that you're getting asked to write the specifications and that means you're already leveraging your influence and getting noticed by management. Start a journal or weblog. The more you write, the easier it will be, and the easier it is to write, the more you'll write, in a virtuous circle.

Learn C

C. Notice I didn't say C++. Although C is becoming increasingly rare, it is still the lingua franca of working programmers. It is the language they use to communicate with one another, and, more importantly, it is much closer to the machine than "modern" languages that you'll be taught in college like ML, Java, Python, whatever trendy junk they teach these days. You need to spend at least a semester getting close to the machine or you'll never be able to create efficient code in higher level languages. You'll never be able to work on compilers and operating systems, which are some of the best programming jobs around. You'll never be trusted to create architectures for large scale projects. I don't care how much you know about continuations and closures and exception handling: if you can't explain why "while (*s++ = *t++);" copies a string, or if that isn't the most natural thing in the world to you, well, you're programming based on superstition, as far as I'm concerned: a medical doctor who doesn't know basic anatomy, passing out prescriptions based on what the pharma sales babe said would work.

some special cases to indicate this point
char bigString[1000];     /* I never know how much to allocate... */

bigString[0] = '\0';
strcat(bigString,"John, ");
strcat(bigString,"Paul, ");

strcat(bigString,"George, ");

strcat(bigString,"Joel ");

The time consumption will increase as the n^2, where n indicates the number of characters that have already in the char array, for the reason that every time the strcat will begin to search at the beginning of the array. To reduce the runtime decrease as linear as input number of values:
char* mystrcat( char* dest, char* src )

{
     while (*dest) dest++;

     while (*dest++ = *src++);
     return --dest;
}
char bigString[1000];     /* I never know how much to allocate... */
char *p = bigString;

bigString[0] = '\0';

p = mystrcat(p,"John, ");
p = mystrcat(p,"Paul, ");

p = mystrcat(p,"George, ");
p = mystrcat(p,"Joel ");

The designers of Pascal were aware of this problem and "fixed" it by storing a byte count in the first byte of the string. These are called Pascal Strings. They can contain zeros and are not null terminated. Because a byte can only store numbers between 0 and 255, Pascal strings are limited to 255 bytes in length, but because they are not null terminated they occupy the same amount of memory as ASCIZ strings. The great thing about Pascal strings is that you never have to have a loop just to figure out the length of your string. Finding the length of a string in Pascal is one assembly instruction instead of a whole loop. It is monumentally faster.

The old Macintosh operating system used Pascal strings everywhere. Many C programmers on other platforms used Pascal strings for speed. Excel uses Pascal strings internally which is why strings in many places in Excel are limited to 255 bytes, and it's also one reason Excel is blazingly fast.

For a long time, if you wanted to put a Pascal string literal in your C code, you had to write:

char* str = "\006Hello!";

Yep, you had to count the bytes by hand, yourself, and hardcode it into the first byte of your string. Lazy programmers would do this, and have slow programs:

char* str = "*Hello!";
str[0] = strlen(str) - 1;

Notice in this case you've got a string that is null terminated (the compiler did that) as well as a Pascal string. I used to call these fucked strings because it's easier than calling them null terminated pascal strings but this is a rated-G channel so you will have use the longer name.

Well, since we're looking at the bits today I shouldn't have ignored this. I should have done this correctly: figured out how many bytes I needed and allocated the right amount of memory. Shouldn't I have?

Because otherwise, you see, a clever hacker will read my code and notice that I'm only allocating 1000 bytes and hoping it will be enough, and they'll find some clever way to trick me into strcatting a 1100 byte string into my 1000 bytes of memory, thus overwriting the stack frame and changing the return address so that when this function returns, it executes some code which the hacker himself wrote. This is what they're talking about when they say that a particular program has a buffer overflow susceptibility. It was the number one cause of hacks and worms in the olden days before Microsoft Outlook made hacking easy enough for teenagers to do.

(bold malloc...)How does the malloc work? The nature of malloc is that it has a long linked list of available blocks of memory called the free chain. When you call malloc, it walks the linked list looking for a block of memory that is big enough for your request. Then it cuts that block into two blocks -- one the size you asked for, the other with the extra bytes, and gives you the block you asked for, and puts the leftover block (if any) back into the linked list. When you call free, it adds the block you freed onto the free chain. Eventually, the free chain gets chopped up into little pieces and you ask for a big piece and there are no big pieces available the size you want. So malloc calls a timeout and starts rummaging around the free chain, sorting things out, and merging adjacent small free blocks into larger blocks. This takes 3 1/2 days. The end result of all this mess is that the performance characteristic of malloc is that it's never very fast (it always walks the free chain), and sometimes, unpredictably, it's shockingly slow while it cleans up. (This is, incidentally, the same performance characteristic of garbage collected systems, surprise surprise, so all the claims people make about how garbage collection imposes a performance penalty are not entirely true, since typical malloc implementations had the same kind of performance penalty, albeit milder.)

Smart programmers minimize the potential distruption of malloc by always allocating blocks of memory that are powers of 2 in size. You know, 4 bytes, 8 bytes, 16 bytes, 18446744073709551616 bytes, etc. For reasons that should be intuitive to anyone who plays with Lego, this minimizes the amount of weird fragmentation that goes on in the free chain. Although it may seem like this wastes space, it is also easy to see how it never wastes more than 50% of the space. So your program uses no more than twice as much memory as it needs to, which is not that big a deal. Furthermore, when you call realloc, you should always double the size of memory that was previously allocated. That means that you never have to call realloc more than lg n times, which has decent performance characteristics even for huge strings, and you never waste more than 50% of your memory.

tree search algorithm (cont.)

 The previous post is here
============
struct treeNode{
    int element;
    struct treeNode *left;
    struct treeNode *right;
}:
typedef struct treeNode *searchTree;


searchTree makeEmpty(searchTree T){
    if(T!=NULL){
        MakeEmpty(T->left);
        MakeEmpty(T->right);
        free(T);
    }
    return NULL;
}


searchTree findVal(int val, searchTree T){
    if(T==NULL)
        return NULL;
    if(valelement)
        return findVal(val, T->left);
    else if(val>T->element)
        return findVal(val, T->right);
    else
        return T;
}


searchTree findMin(searchTree T){
    if(T!=NULL)
        while(T->left!=NULL)
            T = T->left;
    return T;
}


searchTree insertVal(int val, searchTree T){
    if(T==NULL){
        T=(searchTree)malloc(sizeof(struct treeNode));
        if(T==NULL){
            printf("Error! There is no new memory to allocate.\n");
            exit(0);
        }
        T->element = val;
        T->left = T->right = NULL;
    }
    else{
        if(valelement)
            T->left = insertVal(val, T->left);
        else if(val>T->element)
            T->right = insertVal(val, T->right);
        else
            printf("The element has already in this tree.\n");
    }
    return T;
}


searchTree deleteVal( int val, searchTree T){
    searchTree temp;
    if(T==NULL){
        printf("The element is not found.\n");
        return NULL;
    }
    else if(valelement)
        T->left = deleteVal(val, T->left);
    else if(val>T->element)
        T->right = deleteVal(val, T->right);
    else{        // here, find the specific element
        if(T->left && T->right){
            temp = findMin(T->right);
            T->element = tmp->element;
            T->right = deleteVal(tmp->element, T->right);
        }
        else{
            temp = T;
            if(T->left == NULL)
                T = T->right;
            else if(T->right==NULL)
                T = T->left;
            free(temp);
        }
        return T;
    }
}

// the functions below returns node which element is closest
// and larger in the Tree. We could call it "next"
// assumption1: the inputs are inquiry val and the root node
searchTree nextLarger(int val, searchTree T){
    searchTree temp;
    if(T==NULL){
        printf("There is no tree.\n");
        return NULL;
    }
    if(valelement){
        if(T->left!=NULL){
            temp = T->left;
            while(valelement && temp->left!=NULL){
                T = temp;
                temp = temp->left;
            }
            // This case indicate "temp->left==NULL" causes stop
            // so temp should be the return value
            if(valelement)
                T = temp;
            // otherwise, result might in a new right tree
            // . or the parent node in this layer
            else{
                if (temp->right!=NULL){
                    temp = nextLarger(val, temp->right);
                    if (temp!=NULL)
                        T = temp;
                }
            }
        }
        return T;
    }
    else{
        while(val>=T->element && T->right!=NULL)
            T = T->right;
        if(valelement){
            T = nextLarger(val, T);
            return T;
        }
        else
            return NULL;
    }
}


// assumption2: the input value is a given node in the tree.
// In this case, we might have to trace back.
// As a resutl, the original struct needs a little modification
struct treeNode{
    int element;
    struct treeNode *left;
    struct treeNode *right;
    struct treeNode *parenet;    // to trace back
}:
typedef struct treeNode *searchTree;

searchTree nextLarger2(searchTree start){
    searchTree temp, record;
    if(start==NULL){
        printf("There is not a valid input.\n");
        return NULL;
    }
   
    if(start->right!=NULL){
        start = findMin(start->right);
        return start;
    }
    else if(start->parent!=NULL){
        if(start == start->parent->left)
            return start;
        else{
            while(start->parent!=NULL && start!=start->parent->left)
                start = start->parent;
            if(start==start->parent->left)
                return start;
            else
                return NULL;
        }
    }
}


// references: <Introduction to algorithms>, <Coding Interviews>

// I just did some terrible interviews these days. Yes, some, and terrible.
// So, I wanna record everything here, 
// no matter how stupid and rudimentary it is.
// Also as a means to push myself, everyday a step further.

tree search algorithms

// Breadth-First Search
// The tricky part is that we have to know the entire info. about
// the graph, which indicates in the link-matrix graphmatrix

struct node{
    int color;    // 0-white, 1-grey, 2-black
    int index;    // fount order
    int d;         // distance to the root
    struct node *parent;
};
typedef struct node* Node;

void buildBFS1(int *graphmatrix, Node graph, Node start){
    int i=0, n, head, tail;
    Node queue;    // used as stack to do BFS
    Node temp;

    while(graph[i]!=NULL){
        graph[i].color = 0;
        graph[i].index = i;
        graph[i].parent = NULL;
        graph[i].d = 0;
        i++;
    }
    n = i;
    start->color = 1;
    queue = (Node)malloc(n*sizeof(Node));    // not sure here...
    head = tail = 0;
    enqueue(queue, &tail, start);

    while(!isEmpty(head, tail)){
        temp = dequeue(queue, &head);
        for (i=0; i
            if(graphMatrix[temp->index][i]!=0){
                if(graph[i].color==0){
                    graph[i].color = 1;
                    graph[i].d = temp->d+1;
                    graph[i].parent = temp;
                    enqueue(queue, &tail, graph[i]);
                }
            }
        }
        temp->color = 2;
    }
}

void initQueue(int *head, int *tail){
    *head = *tail =0;
}

void enqueue(Node q, int *tail, Node element){
    q[(*tail)++]=element;
}

Node dequeue(Node q, int *head){
    return q[(*head)++];
}

int isEmpty(int head, int tail){
    return head==tail? 1:0;
}

int isFull(int tail, const int size){
    return tail==size? 1:0;
}


// Depth-First Search
// has more knowledge about the structure of the tree
// at the cost of a more complicated struct

struct node{
    int index;
    int color;
    int detected;
    int finished;
    struct node *parent;
}
typedef struct node* Node;

// the original algorithm in the textbook is a little bit wierd
// cause it is different from BFS by no need of starting point
// while it is obvious that starting with different points will
// generate trees with different structures, given the same link-matrix
void buildDFS(int *graphMatrx, Node graph, Node start){
    int i=0, n, time;
    Node temp;
    while(graph[i]!=NULL){
        graph[i].color = 0;
        graph[i].parent = NULL;
        graph[i].detected = graph[i].finished = 0;
        graph[i].index = i;
        i++;
    }
    n = i;
    time = 0;
    graph[1] = temp;
    graph[1] = start;
    start = temp;    // just want to start at the beginning of the array
    while(i>=0){
        if(graph[i].color == 0)
            visitDFS(graphMatrix, graph, i, &time, n);
        i--;
    }
}

void visitDFS(int *graphMatrix, Node graph, int i, int *time, int length){
    graph[i].color = 1;    // grey, begin to visit
    graph[i].detected = ++(*time);
    for (int j=0; j
        if(graphMatrix[graph[i].index][j]!=0){
            if(graph[j].color == 0){
                graph[j].parent = &graph[i];
                visitDFS(graphMatrix, graph, j, time, length);
            }
        }
    }
    graph[i].color = 2;    // black, conclude the visiting
    graph[i].finished = ++(*time);
}

(to be continued)        
=========

reference: <Introduction to algorithms>

some abstract

说到Unix为我们所带来的软件开发的哲学，我必需要说一说。Unix遵循的原则是KISS（Keep it simple, stupid）。在http://en.wikipedia.org/wiki/Unix_philosophy 上有很多的基本上大同小异的Unix哲学，都是很经典的。

Doug McIlroy 是认为UNIX的哲学是这样的：三条哲学，简明扼要，就是这三条哲学贯穿着整个Unix世界。尤其是第一条“do one thing and do it well”真是相当精彩！

    * Write programs that do one thing and do it well.
    * Write programs to work together.
    * Write programs to handle text streams, because that is a universal interface.

只要是Unix的程序员，他们会比别的程序员在任何时候都会不停地强调着这三条哲学。

而《The Art of Unix Programming》总结了下面这些哲学，都是至理名言啊。

    * Rule of Modularity: Write simple parts connected by clean interfaces.
    * Rule of Clarity: Clarity is better than cleverness.
    * Rule of Composition: Design programs to be connected to other programs.
    * Rule of Separation: Separate policy from mechanism; separate interfaces from engines.
    * Rule of Simplicity: Design for simplicity; add complexity only where you must.
    * Rule of Parsimony: Write a big program only when it is clear by demonstration that nothing else will do.
    * Rule of Transparency: Design for visibility to make inspection and debugging easier.
    * Rule of Robustness: Robustness is the child of transparency and simplicity.
    * Rule of Representation: Fold knowledge into data so program logic can be stupid and robust.
    * Rule of Least Surprise: In interface design, always do the least surprising thing.
    * Rule of Silence: When a program has nothing surprising to say, it should say nothing.
    * Rule of Repair: When you must fail, fail noisily and as soon as possible.
    * Rule of Economy: Programmer time is expensive; conserve it in preference to machine time.
    * Rule of Generation: Avoid hand-hacking; write programs to write programs when you can.
    * Rule of Optimization: Prototype before polishing. Get it working before you optimize it.
    * Rule of Diversity: Distrust all claims for “one true way”.
    * Rule of Extensibility: Design for the future, because it will be here sooner than you think.

X Windows 的设计者 Mike Gancarz 给出了下面九条哲学思想

   1. Small is beautiful.
   2. Make each program do one thing well.
   3. Build a prototype as soon as possible.
   4. Choose portability over efficiency.
   5. Store data in flat text files.
   6. Use software leverage to your advantage.
   7. Use shell scripts to increase leverage and portability.
   8. Avoid captive user interfaces.
   9. Make every program a filter.


十条不错的编程观点
1） The only “best practice” you should be using all the time is “Use Your Brain”, rather than some so-called "famous" frameworks, methods, classes, or prototypes.
2）Programmers who don’t code in their spare time for fun will never become as good as those that do.
3）Most comments in code are in fact a pernicious form of code duplication, which should explain "why", rather than "how" and "what".
4）XML is highly overrated
5）Not all programmers are created equal
6）”Googling it” is okay!
7）If you only know one language, no matter how well you know it, you’re not a great programmer.
8）Your job is to put yourself out of work. Or, saying, if you can’t be replaced then you can’t be promoted!
9）Design patterns are hurting good design more than they’re helping it.
10）Unit Testing won’t help you write good code

job hunting

need to read:
thinking in Java
coding interviews
thinking in C++
CLRS and K&R, again...

in one month?.. ok, i will try.

Reply: 这七个月

  
其实我应该好好享受最后一个人过的日子
me: 嗯，其实我也是。

参加不靠谱的活动
me: ok~

读不靠谱的书
me: of course, you can

穿不靠谱的衣服
me: 好吧……

学不靠谱的知识。
me: 没问题～

勾引可爱的小学弟
me: 不行！

然后再勾引学长
me: 不行！！

再勾引单身的男老师
me: 必然不行！！！

或者，只是一个人安静一会儿不去想你。
me: 嗯:)

嗯哼～