Scheme lists optimization
« Monday, October 07, 2013 »

Lists Scheme

I recently wrote a simple file loader for 3d models saved in .obj wavefront. As usual, the obj format is probably the easiest to parse to get started with 3d engines. I wrote my first loading version in a couple of minutes. As expected, it didn't come without bugs but it worked for a fairly simple model. While reading the tutorials at: Wikibooks, I finally arived to the part where I should be actually loading models from files. I used the sample suzanne file from the tutorial.

The code I ended up with is the following:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
(define (load-obj filename)

  (define (to-numbers lst)
    (map string->number lst))

  (define (parse-vertex lst)
    (to-numbers
      (map (lambda (str)
        (car (string-split str "/" #t))) lst)))

  (define parse-normal to-numbers)

  (define (parse-element lst)
    (map (lambda (x) (- x 1)) (to-numbers lst)))

  (define (parse-texcoord lst)
    (let ((uvs (to-numbers lst)))
      (if (= (length uvs) 2)
        (append uvs (list 0))
        uvs)))

  (call-with-input-file filename
    (lambda (file)
      (let parse ((line (read-line file))
                  (name "")
                  (vertices (list))
                  (texcoords (list))
                  (normals (list))
                  (elements (list)))

        (if (equal? line #!eof)
          (list name vertices texcoords normals elements)

          (let* ((tokens (string-tokenize line))
                 (type (car tokens))
                 (lst (cdr tokens)))

            (parse (read-line file)
                   (if (equal? type "o") (cadr tokens) name)
                   (if (equal? type "v") (append vertices (parse-vertex lst)) vertices)
                   (if (equal? type "vt") (append texcoords (parse-texcoord lst)) texcoords)
                   (if (equal? type "vn") (append normals (parse-normal lst)) normals)
                   (if (equal? type "f") (append elements (parse-element lst)) elements))))))))

The code should be quite easy to understand, I open a file a read each lines. The function that parse the code is a recursive let that sends itself changed parameters. It sends for each step a new line or #eof. When the end of file is reached, it returns a list containing everything we loaded. On each step, I might push more data in one of the list.

Sounds good let's see how fast does it load a file

0.111s CPU time, 0.057s GC time (major), 19225 mutations, 137/464 GCs (major/minor)

Not bad, but the file is quite small. 28kb. Let's try with a bigger file (471kb). We're getting serious here. the obj file format is text based which means that it isn't optimized for space. It is easy to read/write those files. I wouldn't recommend using those files for games because they might get quite big. Anyway the results!

20.149s CPU time, 9.286s GC time (major), 245342 mutations, 6395/22017 GCs (major/minor)

Looking at this, we realize that yes, it is pretty bad. You can see from those numbers that a lot is going on. That said, loading this file in blender is quite fast. Much more faster than my current loader. When writing the first version of my loader, I predicted that something like this might happen. If you accurately read the code above, you should have noticed that I'm storing points inside lists. Lisps and Schemes make good use of lists but people should keep in mind that lists aren't that efficient if you're adding things at the end… Unfortunately we have to append things to our lists. Before loading the file, we have no idea how many things are going to get loaded. We cannot create a vector with a fixed size that is going to get filled by index.

Complexity of algorithms

I guess it is important to talk about it. I rarely thought about it before but knowing how expensive an algorithm can help us improve it. Lists are cool but appending to a list isn't.

Let say we have a list of 100 lines in which there is 3 points. For each line, we add 3 points to the list and go to the next line. The complexity of this algorithm would be O(n) if we wouldn't be using lists. To append something at the end of the list, we have to walk over each elements in the list.

  • Step1: 0 elements and we append
  • Step2: 3 elements and we append
  • Step3: 6 elements and we append
  • StepN: N * 3 elements and we append

In other words, our complexity is already somewhere close to O(n!).

As our lists grows, we will have to walk a lot more of items to change the last element to our new list. It is quite bad! But not dramatic at all, to speed things up, we can use this tricks. Instead of appending items to our list, we should actually prepend them. We will more than often will have to walk over 3 or 4 items to append the big list.

We'd have to change this

1
(append old parsed_items)

To

1
(append (reverse parsed_items) old)

Since our order matters, we have to reverse the order of the things that we're adding inside our lists before we prepend them. Once we parsed everything, we will have to reverse the list one more time.

The code above, should look like this now:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
(define (load-obj filename)

  (define (to-numbers lst)
    (map string->number lst))

  (define (parse-vertex lst)
    (to-numbers
      (map (lambda (str)
        (car (string-split str "/" #t))) lst)))

  (define parse-normal to-numbers)

  (define (parse-element lst)
    (map (lambda (x) (- x 1))
        (to-numbers
          (map (lambda (str)
            (car (string-split str "/" #t))) lst))))

  (define (parse-texcoord lst)
    (let ((uvs (to-numbers lst)))
      (if (= (length uvs) 2)
        (append uvs (list 0))
        uvs)))

  (call-with-input-file filename
    (lambda (file)
      (let parse ((line (read-line file))
                  (name "")
                  (vertices (list))
                  (texcoords (list))
                  (normals (list))
                  (elements (list)))

        (if (equal? line #!eof)

          ; Return reversed
          (list name
                (reverse vertices)
                (reverse texcoords)
                (reverse normals)
                (reverse elements))

          (let* ((tokens (string-tokenize line))
                 (type (car tokens))
                 (lst (cdr tokens)))

            ; Append reversed
            (parse (read-line file)
                   (if (equal? type "o") (cadr tokens) name)
                   (if (equal? type "v") (append (reverse (parse-vertex lst)) vertices) vertices)
                   (if (equal? type "vt") (append (reverse (parse-texcoord lst)) texcoords) texcoords)
                   (if (equal? type "vn") (append (reverse (parse-normal lst))) normals)
                   (if (equal? type "f") (append (reverse (parse-element lst)) elements) elements))))))))

Now let see how fast, can we beat the old algorithm even if we are still using lists…? How fast can the new version with reversed list can be compared to plain brute append? Behold! The new version of the code is close to be 100 times faster! There is a lot less mutations and almost no time is spent garbage collecting.

0.251s CPU time, 0.046s GC time (major), 371294 mutations, 51/5149 GCs (major/minor)

There are probably ways to make this code even faster, but it should be good enough for now. Keep in mind that the only way someone can benefit of this is when you're appending a small list to a bigger one. Reversing once the big list should take around N operations. The complexity of the new algorithm is close to O(2N). Since we're appending to our big lists with a fixed amount of steps, those steps can be ignored and N is the amount of times we are prepending. Reversing the big list is O(N). O(N) + O(N) = O(2N). It was pretty easy to change our inefficient code in a pretty efficient code. Luckily we could just prepend instead of appending. Linked lists are cool but never forget how they work to get the best advantages from them.

comments powered by Disqus

Copyright © 2015 Loïc Faure-Lacroix