NetBSD Focuses On Scalability

An anonymous reader writes "Felix von Leitner recently performed some benchmarks (previous story) for a talk about scalable network programming he held at Linux Kongress 2003. The winners in this scalability lineup were Linux and FreeBSD 5, followed by NetBSD and finally OpenBSD. What's interesting is that in only two weeks time the NetBSD team made dramatic improvements. Felix performed his benchmarks again and the results are nothing short of astonishing. NetBSD now has better scalability than FreeBSD." Read on for a list of improvements.

the submitter lists these changes:

• socket: previously O(n), now O(1).
  
• bind: greatly improved, but still O(n). Much less steep, though.
  
• fork: a modest O(n) for dynamically linked programs, O(1) for statically linked.
  
• mmap: a bad O(n) before, now O(1) with a small O(n) shadow.
  
• touch after mmap: a bad strange graph in 1.6.1, a modest O(n) a week ago, now O(1).
  
• http request latency: previously O(n), now O(1)

This is a very good job from the NetBSD team! I hope to see more benchmarks and more improvement for a great OS like NetBSD."

Comments

Re:Nice

[someonehasmyname]

Actually, it's OpenBSD that doesn't support SMP. FreeBSD and NetBSD both support it rather well.

Re:What?

[booch]

RTFA - specifically the graph of the mmap benchmark in question. Note that for the most part the red line goes straight across. But there are a few data points that follow a O(n) graph above that (what the author called a shadow). So the interpretation is that the typical case is O(1), but occasionally it has a worst-case performance of O(n). Plus, the factor of the O(n) case is much lower than the previous version.

Re:What?

[Anonymous Coward]

Calm down. If a given implementation is generally O(1) in practice, but can be hit with a case that resorts to an original O(n) algorithm, then their description of "O(1) with a small O(n) shadow" seems like good description. Technically, you must call this O(n) then, since the worst case is O(n). But more information is better in this case, as long as it's accurate.

Re:What?

[platipusrc]

if you have any part of your operation that is O(n) you are O(n) - it's as simple as that.

Nope, you act like you know what you're talking about, but you're forgetting about a fun thing called amortization. For example, if you write a stack, and your push operation takes N operations on the Nth push (when you increase your array, and it can't be on the first push), then you can still end up with a constant push time even though not every push is constant.