XMind

Interview Bible

My Blog: http://csbabel.wordpress.com/ My Twitter: @kenny_yuan

1. Progress: approx 20% finished.

2. Language

   1. Functional Languages

      1. Erlang (learning)

      2. Haskell (TODO)

   2. Imperative Languages

      1. Basic, Visual Basic

      2. C

         1. C89

         2. C99

      3. Obj-C (learning)

         1. Ideas from smalltalk

      4. C++

         1. Libraries

            1. STL

            2. boost

            3. MFC

            4. QT

            5. wxWidget

            6. FFTW

            7. OpenCV

         2. Highlighted Features

            1. RTTI

            2. RAII

            3. Move

               1. RVO

                  1. RValue Ref

            4. POD

               1. A Better Class For Container

            5. C++ 98/03 ISO14882 TR

            6. C++ 0x

         3. Basics

            1. Class: Ctor/Dtor

            2. Function Overloading

               1. Overload Resolution

                  1. Candidate Functions

                     1. Koenig Lookup

                  2. Viable Functions

                  3. Best Match

               2. Operator Overloading

            3. Virtual Function/Polymophism

            4. Template

               1. Container

               2. Declarative Programming

               3. Complile-time Calculating

            5. Exception

            6. To be updated...

   3. Hybrid Languages

      1. LISP

      2. Python

   4. "Little" Language

      1. AWK

      2. Make

      3. Graphviz DOT

      4. Shell

   5. Features

      1. GC

         1. Ref Counting

            1. RefCounting in threads

         2. Mark & Sweep

            1. CMS

         3. Copying

         4. Generation

      2. Type System

         1. Static Type System

            1. Interface & Type(Class)

            2. Template

         2. Dynamic Type System

         3. Meta Type System

         4. Reflection (and also obsolete RTTI)

         5. Type Conversion

            1. Type Promotion

            2. Coercion (Implicit type conversion)

            3. Explicit Conversion

               1. Object Type Cast

                  1. Downcast

                  2. Upcast

            4. Variant

            5. Dynamic Type

      3. Exception

         1. Stack Unwinding

         2. Checked Exception

            1. Violation of OCP

         3. Exception Safty

            1. Exception Safe

               1. Exception Guarantee

                  http://accu.org/index.php/journals/444 Exception Safety Guarantees So far, this article has discussed exception safety without clarifying what that means. It is time to set the record straight. The meaning of the term exception safety is crystallised in the following guarantees (originally formulated by Dave Abrahams): * The basic guarantee - if an operation throws an exception, no resources will leak as a result and invariants (of the component on which the operation is invoked) are preserved * The strong guarantee - additionally, the program's state remains unchanged * The nothrow guarantee - an operation guarantees never to propagate an exception under any circumstances The basic and strong guarantees represent the two levels of exception safety. The purpose of the nothrow guarantee is to enable the basic and strong guarantees to be honoured. Normally, it is the strong guarantee which requires operations promising nothrow, except that destructors must always honour this guarantee (because the destructor might be called as the result of an exception being thrown, with highly undesirable results). The basic guarantee is relatively straightforward to honour: provided resources are managed using the "Execute Around Object" [Henney2000] idiom (a.k.a. "Resource Acquisition is Initialisation" [Stroustrup1997]) - this way, the C++ practice of placing finalisation code in destructors ensures that whichever route an operation exits by, cleanup will be performed. Honouring the strong guarantee is a bit trickier, and more often requires the assistance of the nothrow guarantee... http://en.wikipedia.org/wiki/Exception_handling 1. Failure transparency, also known as the no throw guarantee: Operations are guaranteed to succeed and satisfy all requirements even in presence of exceptional situations. If an exception occurs, it will not throw the exception further up. (Best level of exception safety.) 2. Commit or rollback semantics, also known as strong exception safety or no-change guarantee: Operations can fail, but failed operations are guaranteed to have no side effects so all data retain original values.[2] 3. Basic exception safety: Partial execution of failed operations can cause side effects, but invariants on the state are preserved. Any stored data will contain valid values even if data has different values now from before the exception. 4. Minimal exception safety also known as no-leak guarantee: Partial execution of failed operations may store invalid data but will not cause a crash, and no resources get leaked. 5. No exception safety: No guarantees are made. (Worst level of exception safety)

                  1. Basic Guarantee

                  2. Strong Guarantee

                  3. No-throw Guarantee

               2. Herb Sutter's Guidelines

                  异常安全和异常中立 异常安全（exception-safe）：再出现异常时仍能正常工作 异常中立（exception-neutral）：能将所有异常都转给调用者 Basic Guarantee和Strong Guarantee 关于basic guarantee和strong guarantee的详细论述，请看我在C++ Report Sep/Nov/Dec 1997中的文章。简单来说，basic guarantee保证可销毁性（destructibility）且没有泄漏；而strong guarantee除此之外还保证完全的commit-or-rollback（译注：即“要么执行，要么不执行”的原子规则）语义。 Types of Exception Safety A piece of code can be exception unsafe, neutral, or safe. Exception unsafe code leaks resources and/or leaves partially constructed objects around after an exception is thrown. Exception neutral code passes back all exceptions to the caller. Exception safe code works correctly when exceptions occur and does not leak resources or leave invalid object fragments. There is also basic, strong and no-throw exception safe safety guarantees. The basic exception safety guarantee ensures three things: - Destructors don't throw exceptions(析构函数不抛出异常) - There are no resource leaks(无资源leak) - The state of variables or class instances are valid and useable.(变量或对象的状态是有效的和可用的) The strong exception safety guarantee adds a fourth rule: - The state of an instance is the same before and after if an exception is thrown.(提供原子操作，如果发生异常，实例的状态要同之前一致。类似于数据库的commit或rollback) The no-throw exception safety guarantee adds the most stringent fifth rule: The piece of code will not throw an exception. Guidelines To make this all happen, Herb Sutter [1] has given a series of guidelines: - Ensure that no exception escapes from a destructor, overloaded operator delete() or operator delete[](). - Move all code that might cause an exception into another function or try/catch block; and only when all that code is executes correctly, change the state of the instance. - Give each code fragment (module, class, function) a single well-define responsibility. - Exception safety is a design consideration. It must be built in, not added as an afterthought. - Separate out memory allocation from object construction and destruction. - Use the Resource Acquisition Is Initialization idiom to isolate resource allocation and management. - Use the Acquisition Before Release idiom to ensure that resource is not leaked. - An object may own at most one object (see Griffiths [2]) For basic data types like int and pointer, this is always the case. Acquisition Before Release: 在释放旧的资源前，先获得新的资源，然后交换之。这是异常安全编程的一个基础手法。

                  1. Idiom

                     1. RAII

                        Resource Acquisition Is Initialization idiom

                     2. ABR

                        Acquisition Before Release idiom

                  2. Guidelines

                     Guidelines To make this all happen, Herb Sutter has given a series of guidelines: - Ensure that no exception escapes from a destructor, overloaded operator delete() or operator delete[](). - Move all code that might cause an exception into another function or try/catch block; and only when all that code is executes correctly, change the state of the instance. - Give each code fragment (module, class, function) a single well-define responsibility. - Exception safety is a design consideration. It must be built in, not added as an afterthought. - Separate out memory allocation from object construction and destruction. - Use the Resource Acquisition Is Initialization idiom to isolate resource allocation and management. - Use the Acquisition Before Release idiom to ensure that resource is not leaked. - An object may own at most one object (see Griffiths [2]) For basic data types like int and pointer, this is always the case. Acquisition Before Release: 在释放旧的资源前，先获得新的资源，然后交换之。这是异常安全编程的一个基础手法。

            2. Exception Neutral

            3. Exception, interface, functions & Library

         4. RAII

            1. ScopeGuard

               by Andrei Alexandrescu and Petru Marginean http://www.drdobbs.com/article/printableArticle.jhtml;jsessionid=Z5QPTUN3ED4CPQE1GHPSKHWATMY32JVN?articleId=184403758&dept_url=/cpp/

      4. Metasystem

      5. Multimethod

         1. Object Oriented: Single Dispatch

         2. Visitor Pattern: Double Dispatch

         3. Multimethod: Multiple Dispatch

            1. Generic Function in LISP

      6. Mixin (named by the Icecream Store)

      7. FP Features

         1. High Order Function (or First-class Function)

         2. Evaluation Order

            1. Applicative Order

            2. Normal Order (fully expand and then reduce)

         3. Lambda

         4. Closure

            1. Simulating Closure with Object

         5. Side effect

            1. pure and impure function

            2. monad

         6. Currying

            1. Binders in STL/boost :)

         7. Recursion

            1. Stackless Tail Recursion

            2. Tree Recursion

         8. Fixed Point searching

         9. AMB (AMBiguous function, by John McCarthy)

         10. Continuation

             1. Continuation vs Stack

         11. Pattern Match

         12. List Comprehension

             1. Literate qsort() :)

         13. Map/Reduce

      8. Coroutine

   6. Programming Paradigms

      1. Imperative

         1. Procedural Abstraction

         2. Automata Based Programming

         3. Object Oriented Programming (OOP)

            1. SOLID

               http://www.butunclebob.com/ArticleS.UncleBob.PrinciplesOfOod The Principles of OOD What is object oriented design? What is it all about? What are it's benefits? What are it's costs? It may seem silly to ask these questions in a day and age when virtually every software developer is using an object oriented language of some kind. Yet the question is important because, it seems to me, that most of us use those languages without knowing why, and without knowing how to get the the most benefit out of them. Of all the revolutions that have occurred in our industry, two have been so successful that they have permeated our mentality to the extent that we take them for granted. Structured Programming and Object Oriented Programming. All of our mainstream modern languages are strongly influenced by these two disciplines. Indeed, it has become difficult to write a program that does not have the external appearance of both structured programming and object oriented programming. Our mainstream languages do not have goto, and therefore appear to obey the most famous proscription of structured programming. Most of our mainstream languages are class based and do not support functions or variables that are not within a class, therefore they appear to obey the most obvious trappings of object oriented programming. Programs written in these languages may look structured and object oriented, but looks can be decieving. All too often today's programmers are unaware of the principles that are the foundation of the disciplines that their languages were derived around. In another blog I'll discuss the principles of structured programming. In this blog I want to talk about the principles of object oriented programming. In March of 1995, in comp.object, I wrote an article that was the first glimmer of a set of principles for OOD that I have written about many times since. You'll see them documented in my PPP book, and in many articles on the objectmentor website, including a well known summary. These principles expose the dependency management aspects of OOD as opposed to the conceptualization and modeling aspects. This is not to say that OO is a poor tool for conceptualization of the problem space, or that it is not a good venue for creating models. Certainly many people get value out of these aspects of OO. The principles, however, focus very tightly on dependency management. Dependency Management is an issue that most of us have faced. Whenever we bring up on our screens a nasty batch of tangled legacy code, we are experiencing the results of poor dependency management. Poor dependency managment leads to code that is hard to change, fragile, and non-reusable. Indeed, I talk about several different design smells in the PPP book, all relating to dependency management. On the other hand, when dependencies are well managed, the code remains flexible, robust, and reusable. So dependency management, and therefore these principles, are at the foudation of the -ilities that software developers desire. The first five principles are principles of class design. They are: SRP The Single Responsibility Principle A class should have one, and only one, reason to change. OCP The Open Closed Principle You should be able to extend a classes behavior, without modifying it. LSP The Liskov Substitution Principle Derived classes must be substitutable for their base classes. DIP The Dependency Inversion Principle Depend on abstractions, not on concretions. ISP The Interface Segregation Principle Make fine grained interfaces that are client specific. The next six principles are about packages. In this context a package is a binary deliverable like a .jar file, or a dll as opposed to a namespace like a java package or a C++ namespace. The first three package principles are about package cohesion, they tell us what to put inside packages: REP The Release Reuse Equivalency Principle The granule of reuse is the granule of release. CCP The Common Closure Principle Classes that change together are packaged together. CRP The Common Reuse Principle Classes that are used together are packaged together. The last three principles are about the couplings between packages, and talk about metrics that evaluate the package structure of a system. ADP The Acyclic Dependencies Principle The dependency graph of packages must have no cycles. SDP The Stable Dependencies Principle Depend in the direction of stability. SAP The Stable Abstractions Principle Abstractness increases with stability. Expand All | Collapse All Wed, 11 May 2005 20:27:08, Shane, Buy the Book! I would encourage anyone reading and thinking "I need to know more about this stuff" to buy the book that Bob wrote and refers to (PPP). Expand All | Collapse All Thu, 12 May 2005 10:37:50, Henrik Huttunen, Some praise These principles are taught at our university in a course, where we take second big step toward OO-programming i.e. learning to program with design patterns. I consider the first five to be very important for to get deeper understanding of programming. They've changed my thinking somewhat, and it's nice to check your solution against those principles and see what they might reveal. Also, I have read many articles of yours, and I like them very much. The way you present the problems and different methods to handle them, are clear and profound. And you have made good points about why to write tests before any code; it surely makes programming less painful, when need of debuggin is decreased alot. It's a shame you haven't lately written large articles -- at least don't know any. But at least this blog and newgroup discussing are active. Sincerely, Henrik Expand All | Collapse All Thu, 12 May 2005 11:41:21, Uncle Bob, Writing Large Articles. Henrik, I have a regular column in Software Development magazine. It's called "The Crafstman". In it I write a lot about TDD, Principles, Patterns, and life on a starship. You can see a list of all these article at: http://www.objectmentor.com/resources/listArticles?key=topic&topic=Craftsman I also write feature articles for this magazine from time to time, and for other magazines as well. You can keep track of them, and all the articles the Object Mentors write at http://www.objectmentor.com/resources/articleIndex Expand All | Collapse All Thu, 12 May 2005 12:00:20, Henrik Huttunen, Articles Robert, yes thank you, I'm aware of those. I just wondered you hadn't done any article this year, that's all. Btw. I'm buying a new book about refactoring/TDD/design patterns in general, and would like to hear recommendations. Refactoring to Patterns by Joshua Kerievsky is often recommended, but someone said it has too application specific examples. If someone has read it, I'd like to hear comment on that. Expand All | Collapse All Sun, 15 May 2005 05:13:44, Mauro Marinilli, Praise again and a hint for Henrik I use to read so much about OOP, but your advice always sounds proven and deep. It's something else! Keep up your good, honest work. OOP is too flexible. You can use it for everything and the opposite of everything. That's why it got so popular, perhaps. Principles then are always controverse, though. What happened for example to the fundamentalists of encapsulation (those that refuse to design or even use setter/getters)? Also structured programming isn't a silver bullet, and exaggerating with it make things worse (at least this is what I try to teach to my students.. Shame on me!). That's why your advice is so important: because it is empirically grounded. Henrik: as of Refactoring to Patterns, I'd suggest you to have a look at an earlier draft (http://scholar.google.com/url?sa=U&q=http://www.tarrani.net/RefactoringToPatterns.pdf) that contains half of the patterns but gives you a feeling of the overall approach (sorry if I use this space to reply to another reply). Expand All | Collapse All Mon, 16 May 2005 07:32:54, Henrik Huttunen, Refactoring to Patterns Mauro, thanks for the link :). Expand All | Collapse All Fri, 20 May 2005 19:30:44, Mark Dalrymple, Refactoring to Patterns Refactoring to Patterns is awesome. The examples do deal with real domain-specific code, but the principles are applicable to other domains. Expand All | Collapse All Fri, 20 May 2005 23:15:19, JDCarroll, Almost right You begin by talking about OOD and by the end of the first paragraph have made the most critical of errors: equating OOD with OOP. OOA/D is about THINKING. OOP is about DOING. The two are separate. It took me over half a decade to realize that this wasn't true. OOP and OOD are inseparable. OOA is undefined. - UB And the only criteria by which a OO programming language should be judged is the ability to move from one to the other. Then you move into the notion of Dependency Management as if the way that we think about and write the programs will make it right. Sorry. But whether you live in a Structured world or an Object world the notion of dependancies doesn't change. Folks write code that you depend on. You write code that other folks depend on. Until that changes, we're stuck. No, we aren't stuck. Dependencies are manageable. - UB Expand All | Collapse All Tue, 7 Jun 2005 02:46:09, cheng jing, when and how add database I read your wonderful book < agile software development >, At chapter 19, u implement the payroll system. Now I design a true PayRoll[?] system, but i don't known when and how can i add database detail ? i can add UI first then meet the client's requirement ? I recommend that you concentrate on the business rules first. Don't worry about the UI or the Database at first. Get the business rules (taxes, deductions, etc) to work. Then you can add a database. And finally you can add a UI. - UB Expand All | Collapse All Sun, 12 Jun 2005 04:31:44, Brad Appleton, Where does The Law of Demeter fit? Hi Bob! Granted, the "Law of Demeter" is a style guideline rather than a principle. Nonetheless, I would expect it to be something that could be readily derived from a handful of these principles. Do you agree? if so, how would you derive it? LOD is a matter of dependencies. A statement like system.trunk.line.lineCard.connect() concentrates too much information into a single place. That one line of code knows about four classes! Large knots of dependencies like this are a violation of the OCP. Any change to the data structures causes changes to that line of code. Expand All | Collapse All Mon, 13 Jun 2005 02:35:41, , Expand All | Collapse All Fri, 17 Jun 2005 07:27:50, Denis Krukovsky, SRP with Observable model? Can we start a discussion here? Let's say we have a Model of some entity, say a ForumTopic[?]. We give it the responsibility to represent a forum topic. Now a classic case - we want our Models to be Observable. So we add a responsibility to notify its Observers on state change. SRP violation. How to make ForumTopic[?] respect SRP while apply Observer pattern here? Denis Krukovsky http://dotuseful.sourceforge.net/ http://dkrukovsky.blogspot.com/ You could use the class form of the Adapter Pattern (i.e. Multiple Inheritance) as follows: |ForumTopic| |Observable| A A | | +-------+------+ | |OservableForumTopic| - UB Expand All | Collapse All Mon, 20 Jun 2005 19:59:43, Don, ISP and accessing multiple non-cohesive interfaces Thanks for your Agile Software Development book - a great resource. I have a question concerning ISP. The second paragraph explicitly states that some objects require non-cohesive interfaces. So I have an object O with two non-cohesive interfaces A and B. My question is this - when a client has access to O as an instance of A, and then at some point needs access to O as an instance of B, how is that managed? My instinct tells me to use a factory for the conversion so that the knowledge that A and B are coresident in O is isolated (allowing adapters and other alternatives) but I am not confident. Any advice welcome. Thanks again. Expand All | Collapse All Sat, 9 Jul 2005 00:40:56, Jay Levitt, Principles same w/dynamic languages? I'm reading through PPP tonight, and it's a fascinating book. But the examples you use to illustrate design smells seem to be dependent on the use of a statically-typed language like C++, with solutions involving virtual base classes and/or MI. I'm playing around with Ruby, which has none of the above, and at first blush it seems to me that a lot of the "binding" issues simply don't exist there; LSP is inherently enforced by "duck-typing", and classes can be extended repeatedly in different source files, providing ISP. As such, SRP and OCP just don't seem to matter. Have there been any discussions or articles about how these principles apply to dynamic languages? Expand All | Collapse All Fri, 30 Sep 2005 08:03:26, Brijesh, I finished reading ur book PPP hi uncle bob, I am great fan of yours, i completed reading the book PPP , after reading that book, the way I look at the solution for a given problem is changed , I mean my thought process is changed when i start thinking about the design, thanks a lot for ur marvellous work on this area. thanks Brijesh Expand All | Collapse All Tue, 4 Oct 2005 21:39:38, JeanW[?], Responsibility The book is great. I do have some deeper questions. The one I have been struggling with lately is defining a responsibility. You write, "In the context of the SRP, we define a responsibility to be 'a reason for change.'" However, the word "responsibility" suggests that the root meaning has to do with managing some sort of feature, and that change is just a *symptom* of managing that feature. Other responsibilities lie undiscovered until a change exposes them. But I've had trouble defining what it is. I mean, if all you wanted to convey was "a reason for change," then you could have called it the "Single Reason to Change" principle. So why did you use the word "responsibility"? And is there a deeper definition than "a reason for change"? Expand All | Collapse All Thu, 6 Oct 2005 09:41:53, Uncle Bob, The Single Reason to Change Principle The principle comes from the work of Tom DeMarco[?]. I don't know if he's responsible for the name or whether the name is an accident of some kind. What I can tell you is that the definition of the principle has evolved over the last thirty years. It began as: A module should do one thing, do it well, and do it only. And it has finally transformed into its current form: A module should have one and only one reason to change. Are these two phrases really synonyms? I think so. I think a reasponsibility boils down to a reason to change. For example, consider a payroll module that pays an employee. We could say that the responsibility is "pay employee". However, over time the payment calculation rules change, even though the printed format of the paycheck does not. Later, the format of the check changes but the calculation doesn't. Clearly there are two different responsibilities. Calculation, and format. Expand All | Collapse All Mon, 3 Apr 2006 01:58:28, Amir Khan, Liskov principle related Hi Uncle Bob, I read with great interest the articles written by you. In fact we cover one technical article every monday morning. Today we did Liskov's Substitution Principle. Please forgive me if my question sound too naive. You talked about Factoring as being one way of making classes LSP compliant. For exampe you created LinearObject[?] and sub-classed Line and LineSegment[?] from it. I was wondering what if the derived classes have some methods that cannot be foctored out to a base class. For example if I factor Circle, Rectangle, and Square to make the Shape class and put the Draw method in it. What if I also need to rotate Rectangle and Square but not the Circle. So what would I do? Should I put the Rotate method in the base Shape class and write a degenerative Rotate method in Circle and solid implementations in Rectangle and Square? In general what should I do if my to-be-factored classes have some common behavior yet also have some unique behavior. I shall look forward to hear from you. Regards Amir Khan Karachi, Pakistan

               1. Basic Principles

                  1. OCP

                     1. which is the most important one

                  2. LSP

                     1. Empty child-class test

                  3. DIP

                  4. SRP

                  5. ISP

               2. Package Principles

                  1. REP — The Reuse Release Equivalency Principle

                  2. CCP — The Common Closure Principle

                  3. CRP — The Common Reuse Principle

                  4. ADP — The Acyclic Dependencies Principle

                  5. SDP — The Stable Dependencies Principle

                  6. SAP — The Stable Abstractions Principle

            2. GRASP

               http://en.wikipedia.org/wiki/GRASP_(object-oriented_design) GRASP (object-oriented design) From Wikipedia, the free encyclopedia General Responsibility Assignment Software Patterns (or Principles), abbreviated GRASP, consists of guidelines for assigning responsibility to classes and objects in object-oriented design. The different patterns and principles used in GRASP are: Information Expert, Creator, Controller, Low Coupling, High Cohesion, Polymorphism, Pure Fabrication, Indirection, Protected Variations. All these patterns answer some software problem, and in almost every case these problems are common to almost every software development project. These techniques have not been invented to create new ways of working but to better document and standardize old, tried-and-tested programming principles in object oriented design. It has been said that "the critical design tool for software development is a mind well educated in design principles. It is not the UML or any other technology".[1] Thus, GRASP is really a mental toolset, a learning aid to help in the design of object oriented software. Contents 1 Patterns Creator Information Expert Controller Low Coupling High Cohesion Polymorphism Pure Fabrication Indirection Protected Variations 2 See also 3 References 4 Notes Patterns Creator See also: Factory pattern Creation of objects is one of the most common activities in an object-oriented system. Which class is responsible for creating objects is a fundamental property of the relationship between objects of particular classes. In general, a class B should be responsible for creating instances of class A if one, or preferably more, of the following apply: Instances of B contains or compositely aggregates instances of A Instances of B record instances of A Instances of B closely use instances of A Instances of B have the initializing information for instances of A and pass it on creation. Information Expert See also: Information hiding Information Expert is a principle used to determine where to delegate responsibilities. These responsibilities include methods, computed fields and so on. Using the principle of Information Expert a general approach to assigning responsibilities is to look at a given responsibility, determine the information needed to fulfill it, and then determine where that information is stored. Information Expert will lead to placing the responsibility on the class with the most information required to fulfill it.[2] Controller See also: Model–view–controller The Controller pattern assigns the responsibility of dealing with system events to a non-UI class that represent the overall system or a use case scenario. A Controller object is a non-user interface object responsible for receiving or handling a system event. A use case controller should be used to deal with all system events of a use case, and may be used for more than one use case (for instance, for use cases Create User and Delete User, one can have one UserController, instead of two separate use case controllers). It is defined as the first object beyond the UI layer that receives and coordinates ("controls") a system operation. The controller should delegate to other objects the work that needs to be done; it coordinates or controls the activity. It should not do much work itself. The GRASP Controller can be thought of as being a part of the Application/Service layer [3] (assuming that the application has made an explicit distinction between the App/Service layer and the Domain layer) in an object-oriented system with common layers. Low Coupling Main article: loose coupling Low Coupling is an evaluative pattern, which dictates how to assign responsibilities to support: low dependency between classes; low impact in a class of changes in other classes; high reuse potential; High Cohesion Main article: cohesion (computer science) High Cohesion is an evaluative pattern that attempts to keep objects appropriately focused, manageable and understandable. High cohesion is generally used in support of Low Coupling. High cohesion means that the responsibilities of a given element are strongly related and highly focused. Breaking programs into classes and subsystems is an example of activities that increase the cohesive properties of a system. Alternatively, low cohesion is a situation in which a given element has too many unrelated responsibilities. Elements with low cohesion often suffer from being hard to comprehend, hard to reuse, hard to maintain and adverse to change.[4] Polymorphism Main article: polymorphism in object-oriented programming According to Polymorphism, responsibility of defining the variation of behaviors based on type is assigned to the types for which this variation happens. This is achieved using polymorphic operations. Pure Fabrication See also: service (systems architecture) A pure fabrication is a class that does not represent a concept in the problem domain, specially made up to achieve low coupling, high cohesion, and the reuse potential thereof derived (when a solution presented by the Information Expert pattern does not). This kind of class is called "Service" in Domain-driven design. Indirection See also: delegation pattern The Indirection pattern supports low coupling (and reuse potential) between two elements by assigning the responsibility of mediation between them to an intermediate object. An example of this is the introduction of a controller component for mediation between data (model) and its representation (view) in the Model-view-controller pattern. Protected Variations Main article: delegation pattern The Protected Variations pattern protects elements from the variations on other elements (objects, systems, subsystems) by wrapping the focus of instability with an interface and using polymorphism to create various implementations of this interface. See also Design pattern (computer science) Design Patterns Anemic Domain Model Solid (object-oriented design) References Larman, Craig (2005). Applying UML and Patterns – An Introduction to Object-Oriented Analysis and Design and Iterative Development (3rd ed.). New Jersey: Prentice Hall. ISBN 0-13-148906-2. Notes ^ Larman 2005, p. 272. ^ Larman 2005 chapter 17, section 11. ^ "Application Layer like business facade?". Yahoo! Groups (domaindrivendesign). Retrieved 15 July 2010. ^ Larman 2005, pp. 314–315. Categories: Software design

               1. Creator

               2. Information Expert

               3. Controller

               4. Low Coupling

               5. High Cohesion

               6. Polymorphism

               7. Pure Fabrication

               8. Indirection

               9. Protected Variations

            3. Symptoms of Rotting Design

               1. by Robert C. Martin

                  1. Rigidity

                     Rigidity is the tendency for software to be difficult to change, even in simple ways. Every change causes a cascade of subsequent changes in dependent modules. What begins as a simple two day change to one module grows into a multiweek marathon of change in module after module as the engineers chase the thread of the change through the application.

                  2. Fragility

                     Closely related to rigidity is fragility. Fragility is the tendency of the software to break in many places every time it is changed. Often the breakage occurs in areas that have no conceptual relationship with the area that was changed.

                  3. Immobility

                     Immobility is the inability to reuse software from other projects or from parts of the same project. It often happens that one engineer will discover that he needs a module that is similar to one that another engineer wrote.

                  4. Viscosity

                     Viscosity comes in two forms: viscosity of the design, and viscosity of the environment. When faced with a change, engineers usually find more than one way to make the change. Some of the ways preserve the design, others do not (i.e. they are hacks.) When the design preserving methods are harder to employ than the hacks, then the viscosity of the design is high. It is easy to do the wrong thing, but hard to do the right thing.

            4. Object Oriented Software Construction (the Book)

               1. A book by Bertrand Meyer

                  1. DBC - Design by Contract

                     decrement is -- Decrease counter by one. require item > 0 do item := item - 1 ensure item = old item - 1 end

               2. Modularity

                  1. 5 Criterias

                     1. Modular Decomposability

                        A software construction method satisfies Modular Decomposability if it helps in the task of decomposing a software problem into a small number of less complex subproblems, connected by a simple structure, and independent enough to allow further work to proceed separately on each of them.

                     2. Modular Composability

                        A method satisfies Modular Composability if it favors the production of software elements which may then be freely combined with each other to produce new systems, possibly in an environment quite different from the one in which they were initially developed.

                     3. Modular Understandability

                        A method favors Modular Understandability if it helps produce software in which a human reader can understand each module without having to know the others, or, at worst, by having to examine only a few of the others.

                     4. Modular Continuity

                        A method satisfies Modular Continuity if, in the software architectures that it yields, a small change in a problem specification will trigger a change of just one module, or a small number of modules.

                     5. Modular Protection

                        A method satisfies Modular Protection if it yields architectures in which the effect of an abnormal condition occurring at run time in a module will remain confined to that module, or at worst will only propagate to a few neighboring modules.

                  2. 5 Rules

                     1. Direct Mapping

                        The modular structure devised in the process of building a software system should remain compatible with any modular structure devised in the process of modeling the problem domain.

                     2. Few Interfaces

                        Every module should communicate with as few others as possible.

                     3. Small Interfaces (weak coupling)

                        If two modules communicate, they should exchange as little information as possible.

                     4. Explicit Interfaces

                        Whenever two modules A and B communicate, this must be obvious from the text of A or B or both.

                     5. Information Hiding

                        The designer of every module must select a subset of the module's properties as the official information about the module, to be made available to authors of client modules.

                  3. 5 Principles

                     1. The Linguistic Modular Units Principle

                        Modules must correspond to syntactic units in the language used.

                     2. The Self-Documentation Principle

                        The designer of a module should strive to make all information about the module part of the module itself.

                     3. The Uniform Access Principle

                        All services offered by a module should be available through a uniform notation, which does not betray whether they are implemented through storage or through computation.

                     4. The Open-Closed Principle

                        Modules should be both open and closed.

                     5. The Single Choice Principle

                        Whenever a software system must support a set of alternatives, one and only one module in the system should know their exhaustive list.

         4. Subject Oriented Programming

         5. Aspect Oriented Programming (AOP)

      2. Component Oriented Programming

      3. Concurrency Oriented Programming

      4. Data Driven Programming

      5. Feature Oriented Programming (FOP)

      6. Event Driven

         1. GUI Programming

         2. Service Oriented Programming

         3. Time Driven Programming

      7. Declarative

         1. Functional Programming

         2. C++ Template Programming

      8. Metaprogramming

         1. Attribute Oriented Programming (@OP)

         2. Generic Programming (GP)

            1. Template Meta Programming (TMP)

               1. Policy Based TMP

         3. Language Oriented Programming

            1. Domain Specific Language

            2. Domain Oriented Dialect

         4. Reflective Programming

         5. Generative Programming

      9. Function Level & Value Level

         1. by John Warner Backus

            1. His achievement

               1. FORTRAN

               2. BNF

               3. Research in FP

   7. Design Patterns

      1. In static typed languages

      2. In dynamic languages with "advanced" features (e.g. CLOS)

      3. Deduced by OO Principles (OCP/etc.)

      4. Anti Patterns

         反面模式（Anti-pattern） KornerHill@gmail.com 2008-5-1 原文：http://en.wikipedia.org/wiki/Anti-pattern 译文：http://www.yeeyan.com/articles/view/27472/7244 [前言] design pattern是设计模式，通常是前人在软件开发过程中积累出来的解决一些问题的现成套路，按它们来做可获益无穷。anti-pattern也是一些现成的套路，但它们是现成的错误套路，避免它们则亦可获益无穷。本文译者Korner Hill的更多其它翻译和原创文章可在blog上找到http://blog.csdn.net/KornerHill。 计算机领域内的很多词汇都缺少公认的中文翻译，anti-pattern也是如此，这里译为反面模式，乃是因为它本身是作为反面教材使用的模式。其实直接用“反面教材”更通俗易懂，但这里为了保持它与设计模式之间的内在关联，而使用了“反面模式”一词。 文中有些个别单词没有翻译，一是如bug和bugfix这样在计算机领域内已经广泛使用的词，二是像Staralised这种在字典里都查不到词，三是像perkele这种有文化背景的名字（perkele是芬兰神话里的雷神）。 有些地方即使翻译过来，可能读者还是不一定会明白，毕竟代码的事情不是纸上谈兵。例如Circle-ellipse problem，涉及的概念较多，虽然能翻译过来，但读者若要理解，还是得到wikipedia上再查。 翻译这篇文章确实很不容易，既要英文好，又要有编程的背景，最好还要有西方生活的背景，在下水平有限，很多地方翻译不到位，请各们谅解。 ================================================================================ = 以下是译文部分 ================================================================================ 来自Wikipedia, 自由百科全书 在软件工程中，一个反面模式（anti-pattern或antipattern）指的是在实践中明显出现但又低效或是有待优化的设计模式。 Andrew Koenig在1995年造了anti-pattern这个词，灵感来自于GoF的《设计模式》一书。而这本书则在软件领域发明了“设计模式”（design pattern）一词。三年后antipattern因《AntiPatterns》这本书而获得普及，而它的使用也从软件设计领域扩展到了日常的社会互动中。按《AntiPatterns》作者的说法，可以用至少两个关键因素来把反面模式和不良习惯、错误的实践或糟糕的想法区分开来： * 行动、过程和结构中的一些重复出现的乍一看是有益的，但最终得不偿失的模式 * 在实践中证明且可重复的清晰记录的重构方案 很多反面模式只相当于是错误、咆哮、不可解的问题、或是可能可以避免的糟糕的实践，它们的名字通常都是一些用反话构成的词语。有些时候陷阱（pitfalls）或黑色模式（dark patterns）这些不正式的说法会被用来指代各类反复出现的糟糕的解决方法。因此，一些有争议的候选的反面模式不会被正式承认。 原文：http://en.wikipedia.org/wiki/Anti-pattern 译文：http://www.yeeyan.com/articles/view/27472/7244 [目录] [1. 已知的反面模式] [1.1 组织结构的反面模式] [1.2 项目管理的反面模式] [1.3 团队管理的反面模式] [1.4 分析方式的反面模式] [1.5 通常的设计反面模式] [1.5.1 面向对象设计的反面模式] [1.6 编程方面的反面模式] [1.7 方法学上的反面模式] [1.8 测试反面模式] [1.9 配置管理反面模式] [Contents] [1 Known anti-patterns] [1.1 Organizational anti-patterns] [1.2 Project management anti-patterns] [1.3 Team management anti-patterns] [1.4 Analysis anti-patterns] [1.5 Software design anti-patterns] [1.5.1 Object-oriented design anti-patterns] [1.6 Programming anti-patterns] [1.7 Methodological anti-patterns] [1.8 Testing anti-patterns] [1.9 Configuration management anti-patterns] [1. 已知的反面模式] [1.1 组织结构的反面模式] * 从天而降的责任（accidental ownership）：雇员们接手了一个与当前系统完全无关的系统，在没有合适的训练、学习或关心下就得维护它（在90年代的电话->网络管理员中很常见） * 分析麻痹（Analysis paralysis）：在项目的分析阶段付出的努力太少 * 引擎室里的船长（Captain in the engine room）：团队带头人把时间和精力全花在技术问题上，没有人开船 * 摇钱树（cash cow）：盈利的老产品通常会导致对新产品的自满 * 持续退化（Continuous obsolescence）：不成比例地投入精力把系统移植到新环境下 * 经费转移（Cost migration）：项目经费转移到弱势的部门或商业伙伴那里 * 危机模式（Crisis mode）或救火模式（firefighting mode）：硬是等到火烧屁屁的时候才去解决问题，结果是每个问题都成了危机问题 * 委员会设计（Design by committee）：很多人同时进行设计，却没有统一的看法 * 委员会扩张（Escalation of commitment）：明知错了还不能收回之前的决定 * 英雄模式（Hero-mode）：长期依赖成员的英雄式的努力来满足不可能的任务期限，同时又忽视从一开始就没有注重软件品质带来的损失 * 我早就说过（I told you so）：某人之前的警告没得到重视，事后又被人发现是正确的，并引起了关注 * 主观管理（Management by hope）：认为平静的表象就代表一切顺利 * 通过忽视的管理（Management by neglect）：过多地委任 * 用数字管理（Management by numbers）：过于关注非本质而又不易取得的数字指标 * Perkele管理（Management by perkele）：用完全听不进异议的独裁作风进行管理 * 思考管理（Management by wondering）：希望一个团队定义自己的目标，然后考虑他们要做什么 * 精神危险（Moral hazard）：不让做决定的人知道他的决定会带来什么结果 * 蘑菇管理（Mushroom management）：有事也不通知雇员或是错误地通知（像种蘑菇一样放在黑地里施肥） * 不是这里发明的（Not invented here）：拒绝使用组织外的主意或方案 * 精益求精（Polishing the polish）：把已经完成的项目交给下属去做，禁止他们做其它的事，又报怨他们低效率 * 规模爬行（另外两个类似的词是复杂度陷阱和功能主义者）：不适当控制项目的规模的增加 * 烟囱（Stovepipe）：结构上支持数据主要在上下方面的流动，却禁止平行的通信 * 客户套牢（Vendor lock-in）：使一个系统过于依赖外部提供的部件 * 小提琴弦组织（Violin string organization）：高度调整和裁减却没有灵活性的组织 [1.2 项目管理的反面模式] * 死亡征途（Death march）：除了CEO，每个人都知道这个项目会完蛋。但是真相却被隐瞒下来，直到大限来临 * 拖后腿的无知（Heel dragging blindness）：项目经理的无知拖了后腿。出于某些动机，员工趋向于减少努力来延长项目时限。例如，他们是按时间（而非结果）付费，又没有能顺利转移过去的后续项目 * 烟和镜（Smoke and mirros）：展示还没完成的函数会是怎样 * 软件膨胀（Software bloat）：允许系统的后续版本使用更多的资源 [1.3 团队管理的反面模式] * 缺席的经理（Absentee manager）：经理长时间不出现的情况 * Cage match negotiator：经理用“不惜一切代价也要取胜”的方式来管理 * Doppelganger：某些经理或同事刚才还平易近人，过了一下就变得难于相处 * 无底洞（Fruitless hoops）：经理在做出决定前要求大量的（通常是无意义的）数据 * 黄金小孩（Golden child）：依据人情而不是实际的表现，特殊的责任、机会、认可、奖励被给予团队成员 * 无头苍蝇（Headless chicken）：经理总是处于恐慌中 * 领导而非经理（Leader not manager）：经理是一个好的领导，却缺乏行政和管理能力 * 管理克隆（Managerial cloning）：经理对所有人的雇佣和指导的方法都是一样的：像他们的老板 * 经理而非领导（Manager not leader）：经理能胜任行政和管理职责，却缺乏领导能力 * 指标滥用（Metric abuse）：恶意或是不适当地使用指标 * 好好先生（Mr. nice guy）：经理想成为每个人的朋友 * 鸵鸟（Ostrich）：有些人员整天做些空洞的事情却忽视那些需要在最后期限前被解决的事情还以为会没事，通常更希望看起来很忙，但实际上会浪费和用尽时间 * 平民英雄（Proletariat hero）：口头上称赞普通员工技术如何如何之牛，实际上管理层只是把他们当成棋子，目的是有借口更多的摊派任务以及增加生产目标 * 得势的暴发户（Rising upstart）：指这样一些潜在的新星，他们急不可耐地想要爬上去，不愿花费量些必要的时间去学习和成长 * 海鸥管理（Seagull management）：飞进来，弄得鸡飞狗跳、一片儿狼藉，然后就拍拍屁股走人 * 懦弱的执行者（Spineless executive）：管理者没有勇气来面对当前形势、来承担责任、或是来保护自己的下属 * 三个脑袋的骑士（Three-headed knight）：没有决断力的管理者 * 终极武器（Ultimate weapon）：有些人完全依赖自己的同事或是组织，好像他们自己只是一个导体，把问题全部传给别人 * 热身状态（Warm bodies）：指有些员工几乎不能达到工作的最低要求，因此不断地从一个项目转到另一个项目，或是从一个团队换到另一个团队。 * 只会说是的人（Yes man）：指一些管理者当面对CEO说的每句话都说是，CEO不在的情况 下他可能说的又是另一回事 [1.4 分析方式的反面模式] * 尿布说明（Napkin specification）：把给开发团队的功能或技术说明写在尿布上（即是说，不正式，又缺乏细节），和根本就没有说明一样 * 假需求（Phony requirements）：所有的需求都是通过网络会议或是电话通知给开发团队的，没有任何功能、技术上的说明或其它说明文档 * 火箭说明（Retro-specification）：在项目已经启动之后才开始写技术、功能说明 [1.5 通常的设计反面模式] * 抽象倒置（Abstraction inversion）：不把用户需要的功能直接提供出来，导致他们要 用更上层的函数来重复实现 * 用意不明（Ambiguous viewpoint）：给出一个模型（通常是OOAD，面向对象分析与设计）却没有指出用意何在 * 大泥球（Big ball of mud）：系统的结构不清晰 * 斑点（Blob）：参考上帝对象（God object） * 气体工厂（Gas factory）：复杂到不必要的设计 * 输入问题（Input kludge）：无法指出和实现对不正确的输入的处理 * 接口膨胀（Interface bloat）：把一个接口做得过于强大以至于极其难以实现 * 魔力按键（Magic pushbutton）：直接在接口的代码里编写实现，而不使用抽象 * 竞争危机（Race hazard）：无法知道事件在不同顺序下发生时产生的结果 * 铁轨方案（Railroaded solution）：由于没有预见和在设计方面欠缺灵活性，提出的方案即使很烂，也成了唯一选择 * 重复耦合（Re-coupling）：不必要的对象依赖 * 烟囱系统（Stovepipe system）：根本就不能维护的被病态的组合在一起的组件 * （Staralised schema）：指这样的数据库方案，包含了两种用途的表，一是通用的，另一种是有针对性的 [1.5.1 面向对象设计的反面模式] * 贫血的域模型（Anemic Domain Model）：仅因为每个对象都要有属性和方法，而在使用域模型的时候没有加入非OOP的业务逻辑 * （BaseBean）：继承一个工具类，而不是代理它 * 调用父类（Call super）：需要子类调用父类被重载的方法 * 圆还是椭圆问题（Circle-ellipse problem）：基于变量的子类化关系进行子类化（原句是Subtyping variable-types on the basis of value-subtypes） * 空子类的错误（Empty subclass failure）：创建不能通过“空子类测试”的类，因为它和直接从它继承而来没有做其它任何修改的子类表现得不同 * 上帝对象（God object）：在设计的单一部分（某个类）集中了过多的功能 * 对象粪池（Object cesspool）：复用那些不满足复用条件的对象 * 不羁的对象（Object orgy）：没有成功封装对象，外部可以不受限制地访问它的内部 * 幽灵（Poltergeists）：指这样一些对象，它们唯一的作用就是把信息传给其它对象 * 顺序耦合（Sequential coupling）：指这样一些对象，它们的方法必须要按某种特定顺序调用 * 单例爱好者（Singletonitis）：滥用单例（singleton）模式 * 又TMD来一层（Yet Another Fucking Layer）：向程序中添加不必要的层次结构、库或是框架。自从第一本关于编程的模式的书出来之后这就变得很普遍。 * 唷唷问题（Yo-yo problem）：一个结构（例如继承）因为过度分裂而变得难于理解 [1.6 编程方面的反面模式] * 意外的复杂度（Accidental complexity）：向一个方案中引入不必要的复杂度 * 积累再开火（Accumulate and fire）：通过一系列全局变量设置函数的参数 * 在远处行动（Action at distance）：意料之外的在系统分离的部分之间迭代 * 盲目信任（Blind faith）：缺乏对bugfix或子函数返回值的正确性检查 * 船锚（Boat anchor）：在系统中保留无用的部分 * bug磁铁（Bug magnet）：指很少被调用以至于最容易引起错误的代码，或是易出错的构造或实践 * 忙循环（Busy spin）：在等待的时候不断占用CUP，通常是因为采用了重复检查而不是适当的消息机制 * 缓存失败（Caching failure）：错误被修正后忘记把错误标志复位 * 货运崇拜编程（Cargo cult programming）：在不理解的情况下就使用模式和方法 * 检查类型而不是接口（Checking type instead of interface）：仅是需要接口符合条件的情况下却检查对象是否为某个特定类型。可能导致空子类失败 * 代码动力（Code momentum）：过于限制系统的一些部分，因为在其它部分反复对这部分的内容做出假设 * 靠异常编程（Coding by exception）：当有特例被发现时才添加新代码去解决 * 隐藏错误（Error hiding）：在显示给用户之前捕捉到错误信息，要么什么都不显示，要么显示无意义的信息 * 异常处理（Expection handling）：使用编程语言的错误处理系统实现平常的编程逻辑 * 硬编码（Hard code）：在实现过程中对系统环境作假设 * 熔岩流（Lava flow）：保留不想要的（冗余的或是低质量的）代码，仅因为除去这些代码的代价太高或是会带来不可预期的结果 * loop-switch序列（Loop-switch sequence）使用循环结构来编写连续步骤而不是switch语句 * 魔幻数字（Magic numbers）：在算法里直接使用数字，而不解释含义 * 魔幻字符串（Magic strings）：直接在代码里使用常量字符串，例如用来比较，或是作为事件代码 * 猴子工作（Monkey work）：指在一些代码复用性或设计上很差的项目中的反复出现的支持性的代码。通常会被避免或是匆忙完成，因此易于出错，有可能会很快变为bug磁铁。 * Packratting：由于长时间不及时释放动态分配的内存而消耗了过量的内存 * 类似保护（Parallel protectionism）：随着代码变得复杂和脆弱，很容易就克隆出一个类似的的结构，而不是直接往现有的结构中添加一些琐碎的属性 * 巧合编程（Programming by accident）：尝试用试验或是出错的方式解决问题，有时是因为很烂的文档或是一开始就没把东西搞清楚 * 馄饨代码（Ravioli code）：系统中有许多对象都是松散连接的 * 软代码（Soft code）：在配置文件里保存业务逻辑而不是在代码中 * 面条代码（Spaghetti code）：指那些结构上完全不可理解的系统，尤其是因为误用代码结构 * 棉花里放羊毛（Wrapping wool in cottom）：常见的情况是某些类的方法只有一行，就是调用框架的代码，而没有任何其它有用的抽象 [1.7 方法学上的反面模式] * 拷贝粘贴编程（Copy and paste programming）：拷贝（然后修改）现有的代码而不是假造通用的解决方案 * 拆除（De-factoring）：去掉功能，把它转化成文档的过程 * 黄金大锤（Golden hammer）：认为自己最喜欢的解决方案是到处通用的（见：银弹） * 未必有之事（Improbability factor）：认为已知的错误不会出现 * 低处的果子（Low hanging fruit）：先处理更容易的问题而忽略更大更复杂的问题。这个问题有些类似于这种情况：科学、哲学和技术上的发现在早期都比较容易得到，一旦问题已经被人研究过了，再要有所创新就难了 * 不是这里做的（Not built here）：见“重新发明轮子”、“不是这里发明的” * 不成熟的优化（Premature optimization）：在编码的早期追求代码的效率，牺牲了好的设计、可维护性、有时甚至是现实世界的效率 * 转换编程法（Programming by permutation）：试图通过连续修改代码再看是否工作的方式来解决问题 * 重新发明方的轮子（Reinventing the square wheel）：已经有一个很好的方案了，又再搞一个烂方案来替代它 * 重新发明轮子（Reinventing the wheel）：无法采纳现有的成熟的方案 * 银弹（Silver bullet）：认为自己最喜欢的技术方案能解决一个更大的问题 * 测试人员驱动开发（Tester driven development）：软件工程的需求来自bug报告 [1.8 测试反面模式] * 敌意测试（hostile testing）：对抗实际的开发方案，使用过量的测试 * 自身测试（Meta-testing）：过度设计测试过程以至于它本身都需要测试，也被称为“看门人的看门人” * 移动标的（Moving target）：连续修改设计和实现从而逃避现现有的测试过程 * 奴隶测试（Slave testing）：通过发匿名电邮或贿赂的方式控制测试人员，从而达到股东的要求 [1.9 配置管理反面模式] * 依赖的地狱（Dependency hell）：需要的产品的版本导致的问题 * 路径地狱（Classpath hell）：和特定库有关的问题，例如依赖关系和要满足程序运行所需的版本 * 扩展冲突（Extension conflict）：苹果系统在Mac OS X版本之前的不同扩展的问题 * DLL地狱（DLL hell）：不同版本带来的问题，DLL可见性和多版本问题，在微软的Windows上尤为突出 * JAR地狱（JAR hell）：JAR文件不同版本或路径带来的问题，通常是由于不懂类加载模型导致的

         1. Project Management

         2. Organizational

            1. Captain in the engine room

            2. Hero Mode

            3. Management by Numbers

            4. Not Invented Here

            5. Vendor Lock-in

            6. Design by Committee

            7. ...

         3. Team Management

            1. Tester Driven Development

            2. Abuse of Lint

            3. ...

         4. Programming

            1. Hardcoded

            2. Magic Numbers

            3. ...

         5. Methodological

            1. Copy & Paste Programming

            2. Golden Hammer

            3. Premature OPtimization

            4. Reinventing the Wheel (even a square one)

            5. Silver Bullet

            6. ...

         6. Software Design

            1. Big Ball of Mud

            2. Railroaded Solution

            3. Abstraction Inversion

               1. Functors in C++

               2. SVN write-only DB

            4. ...

         7. Object-Oriented Design

            1. God Object

            2. Empty Subclass Failure

            3. Yet Another Fucking Layer

            4. Call Super (Overrided)

            5. ...

         8. Testing

            1. Hostile Testing

            2. Meta-Testing (test the test code itself)

            3. Slave Testing (controlling the tester)

            4. ...

   8. Performance Tuning

      1. Do use Profiler

         1. Software Profiler

            1. Generic

            2. Write your own one

         2. Hardware Profiler

            1. DSO/Logic Analyzer/Timer/etc

         3. Profiling via Log

      2. Know exactly what is running in CPU

         1. View ASM

         2. Or Bytecode

         3. Or Preprocessed result

      3. Improving Design

         1. Hardware

            1. Faster Device/Faster Communication Protocol

               1. IOPS/Gbps/latency/RST time/etc

                  1. examples

                     1. Use SSD/RAM Disk

                     2. Use Gbit/10Gbit network

                     3. Use Fiber

                     4. Use PCI Express

                     5. Use CAN Bus

                     6. Use USB 3.0

               2. Upgrade Hardware

                  1. Design for Future? (Moore's Law)

            2. Being Friendly to Hardware

               1. Compiling to SIMD Instructions

               2. Being Friendly to (Associative) Cache

                  1. e.g. Page Coloring

               3. Being Friendly to Pipeline

                  1. e.g. Threaded Code

            3. Using Hardware Acceleration

               1. Using DMA/DSP/GPU/ASIC/etc.

         2. Guarantee of OS: Realtime or Time-sharing?

         3. Using Distributed Architecture

            1. Distributed Database

            2. Google's MapReduce

            3. RAID (a distributed disk architecture)

         4. Improving Business Logic

         5. Space vs. Time

         6. Using Cache/Buffer

            1. Caching Input

               1. Cache provided by CPU/Disk/OS/Program/Server/etc.

            2. Caching Intermediate Result

               Please refer to the Uniform Access Principle.

               1. No side effect: single evaluation

               2. Building Index

               3. Preloading

            3. Caching Output

               1. Output Buffer

                  1. with Battery Protection

            4. Cache Server

               1. Internet Cache Server

               2. Memcached

         7. Organizing Memory

            1. Using Memory Pool

            2. Using Better(suitable) GC Algorithm

               1. CMS/Generation

               2. Avoiding GC thread from "stopping-the-world"

            3. Avoiding Swapping

         8. Batch Operation

         9. Background Operation (fake improvement of performance)

         10. GUI

             1. Update only once after all operations

             2. Only repaint the updated area

             3. Cache visual objects

             4. Use GPU (hardware)

                1. GPU Accelerated 2D Display

             5. OpenGL: Use DisplayList

         11. Parallelism

             1. True Parallelism: Multi Machine/Multi CPU

             2. Concurrency: Multi Process/Thread

                1. Use Thread Pool

                2. Be aware the cost of Locks

                   1. Improving Lock

                      1. e.g. Using read-write-lock

                   2. Messages vs Shared Data

                   3. Async Model

                      1. e.g. kqueue/epoll based model, nginx

                         http://kovyrin.net/2006/04/04/nginx-small-powerful-web-server/ Nginx – Small, But Very Powerful and Efficient Web Server Posted by Scoundrel under Networks · русский Tue 4 Apr 2006 Today, I want to describe one of the interesting tools I am using in my job. This tool is nginx – small, but very powerful and efficient web server created by Igor Sysoev for large Russian web company Rambler and kindly provided by open-source community. This server can be used as standalone HTTP-server and as reverse proxy server before some Apache or another “big” server” to reduce load to backend server by many concurrent HTTP-sessions. As standalone web server, nginx can easily handle huge http-load on static files (images, html-pages, etc). Main features of nginx server: * Handling requests to static content, automatical handling of index files and building directory listings. * Accelerated proxying without caching, simple load banancing and fail-over. * Accelerated support of remote FastCGI servers with simple load banancing and fail-over. * Modules and filters including compression (gzip), byte-ranges, chunked responses, SSI-filter, concurrently executed FastCGI or proxy subrequests from one SSI-page. * SSL-support. Advanced features of nginx server: * IP-based and name-based virtual servers. * Support for keep-alive and pipelined connections. * Flexible configurations like in Apache, tunable timeouts and buffers. * Config file and even executable file updating without any termination in service. * Tunable log files with fast rotation. * Special pages for errors 400-599. * Very efficient URI rewriting with regular expressions. * Access rules based on client’s IP address and on pasword (Basic auth). * Download speed limits. Main architecture specifics of nginx server: * One management and many worker processes; workers are running from non-privileged user. * Support for different techniques for asynchronous sockets handling: kqueue (FreeBSD 4.1+), epoll (Linux 2.6+), rt signals (Linux 2.2.19+), /dev/poll (Solaris 7 11/99+), select and poll. * sendfile() system call support: sendfile (FreeBSD 3.1+), sendfile (Linux 2.2+), sendfile64 (Linux 2.4.21+) and sendfilev (Solaris 8 7/01+). * Accept-filters support on FreeBSD 4.1+ and TCP_DEFER_ACCEPT on Linux 2.4+. * Very efficient memory handling: it needs only 2.5Mbytes of RAM for 10000 inactive keep-alive connections. * Minimum of memory copying operations As an experimental feature, perl interpreper integration can be turned on in nginx. As for my job, we are using nginx as a primary software for free hosting platforms. I have developed specific modules for banner inserting and stats calculation in nginx and now our central server can handle about 150-200Mbit/s of highly fragmented http-traffic (all files are small). I think, this is really good result bacause with any possible tunnings of Apache on the same servers we were not able to handle even 60-80Mbit/s. IMHO, main problem of this server is lack of English documentation. As far as i know, its author is really busy and have no time to translate documentation to English. I hope, this article gave you main ideas of what nginx is and why I think that it is the best of lightweight http-servers in the world. ;-)

                      2. the c10k problem

                         http://www.kegel.com/c10k.html The C10K problem [Help save the best Linux news source on the web -- subscribe to Linux Weekly News!] It's time for web servers to handle ten thousand clients simultaneously, don't you think? After all, the web is a big place now. And computers are big, too. You can buy a 1000MHz machine with 2 gigabytes of RAM and an 1000Mbit/sec Ethernet card for $1200 or so. Let's see - at 20000 clients, that's 50KHz, 100Kbytes, and 50Kbits/sec per client. It shouldn't take any more horsepower than that to take four kilobytes from the disk and send them to the network once a second for each of twenty thousand clients. (That works out to $0.08 per client, by the way. Those $100/client licensing fees some operating systems charge are starting to look a little heavy!) So hardware is no longer the bottleneck. In 1999 one of the busiest ftp sites, cdrom.com, actually handled 10000 clients simultaneously through a Gigabit Ethernet pipe. As of 2001, that same speed is now being offered by several ISPs, who expect it to become increasingly popular with large business customers. And the thin client model of computing appears to be coming back in style -- this time with the server out on the Internet, serving thousands of clients. With that in mind, here are a few notes on how to configure operating systems and write code to support thousands of clients. The discussion centers around Unix-like operating systems, as that's my personal area of interest, but Windows is also covered a bit. Contents * The C10K problem * Related Sites * Book to Read First * I/O frameworks * I/O Strategies 1. Serve many clients with each thread, and use nonblocking I/O and level-triggered readiness notification o The traditional select() o The traditional poll() o /dev/poll (Solaris 2.7+) o kqueue (FreeBSD, NetBSD) 2. Serve many clients with each thread, and use nonblocking I/O and readiness change notification o epoll (Linux 2.6+) o Polyakov's kevent (Linux 2.6+) o Drepper's New Network Interface (proposal for Linux 2.6+) o Realtime Signals (Linux 2.4+) o Signal-per-fd o kqueue (FreeBSD, NetBSD) 3. Serve many clients with each thread, and use asynchronous I/O and completion notification 4. Serve one client with each server thread o LinuxThreads (Linux 2.0+) o NGPT (Linux 2.4+) o NPTL (Linux 2.6, Red Hat 9) o FreeBSD threading support o NetBSD threading support o Solaris threading support o Java threading support in JDK 1.3.x and earlier o Note: 1:1 threading vs. M:N threading 5. Build the server code into the kernel * Comments * Limits on open filehandles * Limits on threads * Java issues [Updated 27 May 2001] * Other tips o Zero-Copy o The sendfile() system call can implement zero-copy networking. o Avoid small frames by using writev (or TCP_CORK) o Some programs can benefit from using non-Posix threads. o Caching your own data can sometimes be a win. * Other limits * Kernel Issues * Measuring Server Performance * Examples o Interesting select()-based servers o Interesting /dev/poll-based servers o Interesting kqueue()-based servers o Interesting realtime signal-based servers o Interesting thread-based servers o Interesting in-kernel servers * Other interesting links Related Sites In October 2003, Felix von Leitner put together an excellent web page and presentation about network scalability, complete with benchmarks comparing various networking system calls and operating systems. One of his observations is that the 2.6 Linux kernel really does beat the 2.4 kernel, but there are many, many good graphs that will give the OS developers food for thought for some time. (See also the Slashdot comments; it'll be interesting to see whether anyone does followup benchmarks improving on Felix's results.) Book to Read First If you haven't read it already, go out and get a copy of Unix Network Programming : Networking Apis: Sockets and Xti (Volume 1) by the late W. Richard Stevens. It describes many of the I/O strategies and pitfalls related to writing high-performance servers. It even talks about the 'thundering herd' problem. And while you're at it, go read Jeff Darcy's notes on high-performance server design. (Another book which might be more helpful for those who are *using* rather than *writing* a web server is Building Scalable Web Sites by Cal Henderson.) I/O frameworks Prepackaged libraries are available that abstract some of the techniques presented below, insulating your code from the operating system and making it more portable. * ACE, a heavyweight C++ I/O framework, contains object-oriented implementations of some of these I/O strategies and many other useful things. In particular, his Reactor is an OO way of doing nonblocking I/O, and Proactor is an OO way of doing asynchronous I/O. * ASIO is an C++ I/O framework which is becoming part of the Boost library. It's like ACE updated for the STL era. * libevent is a lightweight C I/O framework by Niels Provos. It supports kqueue and select, and soon will support poll and epoll. It's level-triggered only, I think, which has both good and bad sides. Niels has a nice graph of time to handle one event as a function of the number of connections. It shows kqueue and sys_epoll as clear winners. * My own attempts at lightweight frameworks (sadly, not kept up to date): o Poller is a lightweight C++ I/O framework that implements a level-triggered readiness API using whatever underlying readiness API you want (poll, select, /dev/poll, kqueue, or sigio). It's useful for benchmarks that compare the performance of the various APIs. This document links to Poller subclasses below to illustrate how each of the readiness APIs can be used. o rn is a lightweight C I/O framework that was my second try after Poller. It's lgpl (so it's easier to use in commercial apps) and C (so it's easier to use in non-C++ apps). It was used in some commercial products. * Matt Welsh wrote a paper in April 2000 about how to balance the use of worker thread and event-driven techniques when building scalable servers. The paper describes part of his Sandstorm I/O framework. * Cory Nelson's Scale! library - an async socket, file, and pipe I/O library for Windows I/O Strategies Designers of networking software have many options. Here are a few: * Whether and how to issue multiple I/O calls from a single thread o Don't; use blocking/synchronous calls throughout, and possibly use multiple threads or processes to achieve concurrency o Use nonblocking calls (e.g. write() on a socket set to O_NONBLOCK) to start I/O, and readiness notification (e.g. poll() or /dev/poll) to know when it's OK to start the next I/O on that channel. Generally only usable with network I/O, not disk I/O. o Use asynchronous calls (e.g. aio_write()) to start I/O, and completion notification (e.g. signals or completion ports) to know when the I/O finishes. Good for both network and disk I/O. * How to control the code servicing each client o one process for each client (classic Unix approach, used since 1980 or so) o one OS-level thread handles many clients; each client is controlled by: + a user-level thread (e.g. GNU state threads, classic Java with green threads) + a state machine (a bit esoteric, but popular in some circles; my favorite) + a continuation (a bit esoteric, but popular in some circles) o one OS-level thread for each client (e.g. classic Java with native threads) o one OS-level thread for each active client (e.g. Tomcat with apache front end; NT completion ports; thread pools) * Whether to use standard O/S services, or put some code into the kernel (e.g. in a custom driver, kernel module, or VxD) The following five combinations seem to be popular: 1. Serve many clients with each thread, and use nonblocking I/O and level-triggered readiness notification 2. Serve many clients with each thread, and use nonblocking I/O and readiness change notification 3. Serve many clients with each server thread, and use asynchronous I/O 4. serve one client with each server thread, and use blocking I/O 5. Build the server code into the kernel 1. Serve many clients with each thread, and use nonblocking I/O and level-triggered readiness notification ... set nonblocking mode on all network handles, and use select() or poll() to tell which network handle has data waiting. This is the traditional favorite. With this scheme, the kernel tells you whether a file descriptor is ready, whether or not you've done anything with that file descriptor since the last time the kernel told you about it. (The name 'level triggered' comes from computer hardware design; it's the opposite of 'edge triggered'. Jonathon Lemon introduced the terms in his BSDCON 2000 paper on kqueue().) Note: it's particularly important to remember that readiness notification from the kernel is only a hint; the file descriptor might not be ready anymore when you try to read from it. That's why it's important to use nonblocking mode when using readiness notification. An important bottleneck in this method is that read() or sendfile() from disk blocks if the page is not in core at the moment; setting nonblocking mode on a disk file handle has no effect. Same thing goes for memory-mapped disk files. The first time a server needs disk I/O, its process blocks, all clients must wait, and that raw nonthreaded performance goes to waste. This is what asynchronous I/O is for, but on systems that lack AIO, worker threads or processes that do the disk I/O can also get around this bottleneck. One approach is to use memory-mapped files, and if mincore() indicates I/O is needed, ask a worker to do the I/O, and continue handling network traffic. Jef Poskanzer mentions that Pai, Druschel, and Zwaenepoel's 1999 Flash web server uses this trick; they gave a talk at Usenix '99 on it. It looks like mincore() is available in BSD-derived Unixes like FreeBSD and Solaris, but is not part of the Single Unix Specification. It's available as part of Linux as of kernel 2.3.51, thanks to Chuck Lever. But in November 2003 on the freebsd-hackers list, Vivek Pei et al reported very good results using system-wide profiling of their Flash web server to attack bottlenecks. One bottleneck they found was mincore (guess that wasn't such a good idea after all) Another was the fact that sendfile blocks on disk access; they improved performance by introducing a modified sendfile() that return something like EWOULDBLOCK when the disk page it's fetching is not yet in core. (Not sure how you tell the user the page is now resident... seems to me what's really needed here is aio_sendfile().) The end result of their optimizations is a SpecWeb99 score of about 800 on a 1GHZ/1GB FreeBSD box, which is better than anything on file at spec.org. There are several ways for a single thread to tell which of a set of nonblocking sockets are ready for I/O: * The traditional select() Unfortunately, select() is limited to FD_SETSIZE handles. This limit is compiled in to the standard library and user programs. (Some versions of the C library let you raise this limit at user app compile time.) See Poller_select (cc, h) for an example of how to use select() interchangeably with other readiness notification schemes. * The traditional poll() There is no hardcoded limit to the number of file descriptors poll() can handle, but it does get slow about a few thousand, since most of the file descriptors are idle at any one time, and scanning through thousands of file descriptors takes time. Some OS's (e.g. Solaris 8) speed up poll() et al by use of techniques like poll hinting, which was implemented and benchmarked by Niels Provos for Linux in 1999. See Poller_poll (cc, h, benchmarks) for an example of how to use poll() interchangeably with other readiness notification schemes. * /dev/poll This is the recommended poll replacement for Solaris. The idea behind /dev/poll is to take advantage of the fact that often poll() is called many times with the same arguments. With /dev/poll, you get an open handle to /dev/poll, and tell the OS just once what files you're interested in by writing to that handle; from then on, you just read the set of currently ready file descriptors from that handle. It appeared quietly in Solaris 7 (see patchid 106541) but its first public appearance was in Solaris 8; according to Sun, at 750 clients, this has 10% of the overhead of poll(). Various implementations of /dev/poll were tried on Linux, but none of them perform as well as epoll, and were never really completed. /dev/poll use on Linux is not recommended. See Poller_devpoll (cc, h benchmarks ) for an example of how to use /dev/poll interchangeably with many other readiness notification schemes. (Caution - the example is for Linux /dev/poll, might not work right on Solaris.) * kqueue() This is the recommended poll replacement for FreeBSD (and, soon, NetBSD). See below. kqueue() can specify either edge triggering or level triggering. 2. Serve many clients with each thread, and use nonblocking I/O and readiness change notification Readiness change notification (or edge-triggered readiness notification) means you give the kernel a file descriptor, and later, when that descriptor transitions from not ready to ready, the kernel notifies you somehow. It then assumes you know the file descriptor is ready, and will not send any more readiness notifications of that type for that file descriptor until you do something that causes the file descriptor to no longer be ready (e.g. until you receive the EWOULDBLOCK error on a send, recv, or accept call, or a send or recv transfers less than the requested number of bytes). When you use readiness change notification, you must be prepared for spurious events, since one common implementation is to signal readiness whenever any packets are received, regardless of whether the file descriptor was already ready. This is the opposite of "level-triggered" readiness notification. It's a bit less forgiving of programming mistakes, since if you miss just one event, the connection that event was for gets stuck forever. Nevertheless, I have found that edge-triggered readiness notification made programming nonblocking clients with OpenSSL easier, so it's worth trying. [Banga, Mogul, Drusha '99] described this kind of scheme in 1999. There are several APIs which let the application retrieve 'file descriptor became ready' notifications: * kqueue() This is the recommended edge-triggered poll replacement for FreeBSD (and, soon, NetBSD). FreeBSD 4.3 and later, and NetBSD-current as of Oct 2002, support a generalized alternative to poll() called kqueue()/kevent(); it supports both edge-triggering and level-triggering. (See also Jonathan Lemon's page and his BSDCon 2000 paper on kqueue().) Like /dev/poll, you allocate a listening object, but rather than opening the file /dev/poll, you call kqueue() to allocate one. To change the events you are listening for, or to get the list of current events, you call kevent() on the descriptor returned by kqueue(). It can listen not just for socket readiness, but also for plain file readiness, signals, and even for I/O completion. Note: as of October 2000, the threading library on FreeBSD does not interact well with kqueue(); evidently, when kqueue() blocks, the entire process blocks, not just the calling thread. See Poller_kqueue (cc, h, benchmarks) for an example of how to use kqueue() interchangeably with many other readiness notification schemes. Examples and libraries using kqueue(): o PyKQueue -- a Python binding for kqueue() o Ronald F. Guilmette's example echo server; see also his 28 Sept 2000 post on freebsd.questions. * epoll This is the recommended edge-triggered poll replacement for the 2.6 Linux kernel. On 11 July 2001, Davide Libenzi proposed an alternative to realtime signals; his patch provides what he now calls /dev/epoll www.xmailserver.org/linux-patches/nio-improve.html. This is just like the realtime signal readiness notification, but it coalesces redundant events, and has a more efficient scheme for bulk event retrieval. Epoll was merged into the 2.5 kernel tree as of 2.5.46 after its interface was changed from a special file in /dev to a system call, sys_epoll. A patch for the older version of epoll is available for the 2.4 kernel. There was a lengthy debate about unifying epoll, aio, and other event sources on the linux-kernel mailing list around Halloween 2002. It may yet happen, but Davide is concentrating on firming up epoll in general first. * Polyakov's kevent (Linux 2.6+) News flash: On 9 Feb 2006, and again on 9 July 2006, Evgeniy Polyakov posted patches which seem to unify epoll and aio; his goal is to support network AIO. See: o the LWN article about kevent o his July announcement o his kevent page o his naio page o some recent discussion * Drepper's New Network Interface (proposal for Linux 2.6+) At OLS 2006, Ulrich Drepper proposed a new high-speed asynchronous networking API. See: o his paper, "The Need for Asynchronous, Zero-Copy Network I/O" o his slides o LWN article from July 22 * Realtime Signals This is the recommended edge-triggered poll replacement for the 2.4 Linux kernel. The 2.4 linux kernel can deliver socket readiness events via a particular realtime signal. Here's how to turn this behavior on: /* Mask off SIGIO and the signal you want to use. */ sigemptyset(&sigset); sigaddset(&sigset, signum); sigaddset(&sigset, SIGIO); sigprocmask(SIG_BLOCK, &m_sigset, NULL); /* For each file descriptor, invoke F_SETOWN, F_SETSIG, and set O_ASYNC. */ fcntl(fd, F_SETOWN, (int) getpid()); fcntl(fd, F_SETSIG, signum); flags = fcntl(fd, F_GETFL); flags |= O_NONBLOCK|O_ASYNC; fcntl(fd, F_SETFL, flags); This sends that signal when a normal I/O function like read() or write() completes. To use this, write a normal poll() outer loop, and inside it, after you've handled all the fd's noticed by poll(), you loop calling sigwaitinfo(). If sigwaitinfo or sigtimedwait returns your realtime signal, siginfo.si_fd and siginfo.si_band give almost the same information as pollfd.fd and pollfd.revents would after a call to poll(), so you handle the i/o, and continue calling sigwaitinfo(). If sigwaitinfo returns a traditional SIGIO, the signal queue overflowed, so you flush the signal queue by temporarily changing the signal handler to SIG_DFL, and break back to the outer poll() loop. See Poller_sigio (cc, h) for an example of how to use rtsignals interchangeably with many other readiness notification schemes. See Zach Brown's phhttpd for example code that uses this feature directly. (Or don't; phhttpd is a bit hard to figure out...) [Provos, Lever, and Tweedie 2000] describes a recent benchmark of phhttpd using a variant of sigtimedwait(), sigtimedwait4(), that lets you retrieve multiple signals with one call. Interestingly, the chief benefit of sigtimedwait4() for them seemed to be it allowed the app to gauge system overload (so it could behave appropriately). (Note that poll() provides the same measure of system overload.) * Signal-per-fd Chandra and Mosberger proposed a modification to the realtime signal approach called "signal-per-fd" which reduces or eliminates realtime signal queue overflow by coalescing redundant events. It doesn't outperform epoll, though. Their paper ( www.hpl.hp.com/techreports/2000/HPL-2000-174.html) compares performance of this scheme with select() and /dev/poll. Vitaly Luban announced a patch implementing this scheme on 18 May 2001; his patch lives at www.luban.org/GPL/gpl.html. (Note: as of Sept 2001, there may still be stability problems with this patch under heavy load. dkftpbench at about 4500 users may be able to trigger an oops.) See Poller_sigfd (cc, h) for an example of how to use signal-per-fd interchangeably with many other readiness notification schemes. 3. Serve many clients with each server thread, and use asynchronous I/O This has not yet become popular in Unix, probably because few operating systems support asynchronous I/O, also possibly because it (like nonblocking I/O) requires rethinking your application. Under standard Unix, asynchronous I/O is provided by the aio_ interface (scroll down from that link to "Asynchronous input and output"), which associates a signal and value with each I/O operation. Signals and their values are queued and delivered efficiently to the user process. This is from the POSIX 1003.1b realtime extensions, and is also in the Single Unix Specification, version 2. AIO is normally used with edge-triggered completion notification, i.e. a signal is queued when the operation is complete. (It can also be used with level triggered completion notification by calling aio_suspend(), though I suspect few people do this.) glibc 2.1 and later provide a generic implementation written for standards compliance rather than performance. Ben LaHaise's implementation for Linux AIO was merged into the main Linux kernel as of 2.5.32. It doesn't use kernel threads, and has a very efficient underlying api, but (as of 2.6.0-test2) doesn't yet support sockets. (There is also an AIO patch for the 2.4 kernels, but the 2.5/2.6 implementation is somewhat different.) More info: * The page "Kernel Asynchronous I/O (AIO) Support for Linux" which tries to tie together all info about the 2.6 kernel's implementation of AIO (posted 16 Sept 2003) * Round 3: aio vs /dev/epoll by Benjamin C.R. LaHaise (presented at 2002 OLS) * Asynchronous I/O Suport in Linux 2.5, by Bhattacharya, Pratt, Pulaverty, and Morgan, IBM; presented at OLS '2003 * Design Notes on Asynchronous I/O (aio) for Linux by Suparna Bhattacharya -- compares Ben's AIO with SGI's KAIO and a few other AIO projects * Linux AIO home page - Ben's preliminary patches, mailing list, etc. * linux-aio mailing list archives * libaio-oracle - library implementing standard Posix AIO on top of libaio. First mentioned by Joel Becker on 18 Apr 2003. Suparna also suggests having a look at the the DAFS API's approach to AIO. Red Hat AS and Suse SLES both provide a high-performance implementation on the 2.4 kernel; it is related to, but not completely identical to, the 2.6 kernel implementation. In February 2006, a new attempt is being made to provide network AIO; see the note above about Evgeniy Polyakov's kevent-based AIO. In 1999, SGI implemented high-speed AIO for Linux. As of version 1.1, it's said to work well with both disk I/O and sockets. It seems to use kernel threads. It is still useful for people who can't wait for Ben's AIO to support sockets. The O'Reilly book POSIX.4: Programming for the Real World is said to include a good introduction to aio. A tutorial for the earlier, nonstandard, aio implementation on Solaris is online at Sunsite. It's probably worth a look, but keep in mind you'll need to mentally convert "aioread" to "aio_read", etc. Note that AIO doesn't provide a way to open files without blocking for disk I/O; if you care about the sleep caused by opening a disk file, Linus suggests you should simply do the open() in a different thread rather than wishing for an aio_open() system call. Under Windows, asynchronous I/O is associated with the terms "Overlapped I/O" and IOCP or "I/O Completion Port". Microsoft's IOCP combines techniques from the prior art like asynchronous I/O (like aio_write) and queued completion notification (like when using the aio_sigevent field with aio_write) with a new idea of holding back some requests to try to keep the number of running threads associated with a single IOCP constant. For more information, see Inside I/O Completion Ports by Mark Russinovich at sysinternals.com, Jeffrey Richter's book "Programming Server-Side Applications for Microsoft Windows 2000" (Amazon, MSPress), U.S. patent #06223207, or MSDN. 4. Serve one client with each server thread ... and let read() and write() block. Has the disadvantage of using a whole stack frame for each client, which costs memory. Many OS's also have trouble handling more than a few hundred threads. If each thread gets a 2MB stack (not an uncommon default value), you run out of *virtual memory* at (2^30 / 2^21) = 512 threads on a 32 bit machine with 1GB user-accessible VM (like, say, Linux as normally shipped on x86). You can work around this by giving each thread a smaller stack, but since most thread libraries don't allow growing thread stacks once created, doing this means designing your program to minimize stack use. You can also work around this by moving to a 64 bit processor. The thread support in Linux, FreeBSD, and Solaris is improving, and 64 bit processors are just around the corner even for mainstream users. Perhaps in the not-too-distant future, those who prefer using one thread per client will be able to use that paradigm even for 10000 clients. Nevertheless, at the current time, if you actually want to support that many clients, you're probably better off using some other paradigm. For an unabashedly pro-thread viewpoint, see Why Events Are A Bad Idea (for High-concurrency Servers) by von Behren, Condit, and Brewer, UCB, presented at HotOS IX. Anyone from the anti-thread camp care to point out a paper that rebuts this one? :-) LinuxThreads LinuxTheads is the name for the standard Linux thread library. It is integrated into glibc since glibc2.0, and is mostly Posix-compliant, but with less than stellar performance and signal support. NGPT: Next Generation Posix Threads for Linux NGPT is a project started by IBM to bring good Posix-compliant thread support to Linux. It's at stable version 2.2 now, and works well... but the NGPT team has announced that they are putting the NGPT codebase into support-only mode because they feel it's "the best way to support the community for the long term". The NGPT team will continue working to improve Linux thread support, but now focused on improving NPTL. (Kudos to the NGPT team for their good work and the graceful way they conceded to NPTL.) NPTL: Native Posix Thread Library for Linux NPTL is a project by Ulrich Drepper (the benevolent dict^H^H^H^Hmaintainer of glibc) and Ingo Molnar to bring world-class Posix threading support to Linux. As of 5 October 2003, NPTL is now merged into the glibc cvs tree as an add-on directory (just like linuxthreads), so it will almost certainly be released along with the next release of glibc. The first major distribution to include an early snapshot of NPTL was Red Hat 9. (This was a bit inconvenient for some users, but somebody had to break the ice...) NPTL links: * Mailing list for NPTL discussion * NPTL source code * Initial announcement for NPTL * Original whitepaper describing the goals for NPTL * Revised whitepaper describing the final design of NPTL * Ingo Molnar's first benchmark showing it could handle 10^6 threads * Ulrich's benchmark comparing performance of LinuxThreads, NPTL, and IBM's NGPT. It seems to show NPTL is much faster than NGPT. Here's my try at describing the history of NPTL (see also Jerry Cooperstein's article): In March 2002, Bill Abt of the NGPT team, the glibc maintainer Ulrich Drepper, and others met to figure out what to do about LinuxThreads. One idea that came out of the meeting was to improve mutex performance; Rusty Russell et al subsequently implemented fast userspace mutexes (futexes)), which are now used by both NGPT and NPTL. Most of the attendees figured NGPT should be merged into glibc. Ulrich Drepper, though, didn't like NGPT, and figured he could do better. (For those who have ever tried to contribute a patch to glibc, this may not come as a big surprise :-) Over the next few months, Ulrich Drepper, Ingo Molnar, and others contributed glibc and kernel changes that make up something called the Native Posix Threads Library (NPTL). NPTL uses all the kernel enhancements designed for NGPT, and takes advantage of a few new ones. Ingo Molnar described the kernel enhancements as follows: While NPTL uses the three kernel features introduced by NGPT: getpid() returns PID, CLONE_THREAD and futexes; NPTL also uses (and relies on) a much wider set of new kernel features, developed as part of this project. Some of the items NGPT introduced into the kernel around 2.5.8 got modified, cleaned up and extended, such as thread group handling (CLONE_THREAD). [the CLONE_THREAD changes which impacted NGPT's compatibility got synced with the NGPT folks, to make sure NGPT does not break in any unacceptable way.] The kernel features developed for and used by NPTL are described in the design whitepaper, http://people.redhat.com/drepper/nptl-design.pdf ... A short list: TLS support, various clone extensions (CLONE_SETTLS, CLONE_SETTID, CLONE_CLEARTID), POSIX thread-signal handling, sys_exit() extension (release TID futex upon VM-release), the sys_exit_group() system-call, sys_execve() enhancements and support for detached threads. There was also work put into extending the PID space - eg. procfs crashed due to 64K PID assumptions, max_pid, and pid allocation scalability work. Plus a number of performance-only improvements were done as well. In essence the new features are a no-compromises approach to 1:1 threading - the kernel now helps in everything where it can improve threading, and we precisely do the minimally necessary set of context switches and kernel calls for every basic threading primitive. One big difference between the two is that NPTL is a 1:1 threading model, whereas NGPT is an M:N threading model (see below). In spite of this, Ulrich's initial benchmarks seem to show that NPTL is indeed much faster than NGPT. (The NGPT team is looking forward to seeing Ulrich's benchmark code to verify the result.) FreeBSD threading support FreeBSD supports both LinuxThreads and a userspace threading library. Also, a M:N implementation called KSE was introduced in FreeBSD 5.0. For one overview, see www.unobvious.com/bsd/freebsd-threads.html. On 25 Mar 2003, Jeff Roberson posted on freebsd-arch: ... Thanks to the foundation provided by Julian, David Xu, Mini, Dan Eischen, and everyone else who has participated with KSE and libpthread development Mini and I have developed a 1:1 threading implementation. This code works in parallel with KSE and does not break it in any way. It actually helps bring M:N threading closer by testing out shared bits. ... And in July 2006, Robert Watson proposed that the 1:1 threading implementation become the default in FreeBsd 7.x: I know this has been discussed in the past, but I figured with 7.x trundling forward, it was time to think about it again. In benchmarks for many common applications and scenarios, libthr demonstrates significantly better performance over libpthread... libthr is also implemented across a larger number of our platforms, and is already libpthread on several. The first recommendation we make to MySQL and other heavy thread users is "Switch to libthr", which is suggestive, also! ... So the strawman proposal is: make libthr the default threading library on 7.x. NetBSD threading support According to a note from Noriyuki Soda: Kernel supported M:N thread library based on the Scheduler Activations model is merged into NetBSD-current on Jan 18 2003. For details, see An Implementation of Scheduler Activations on the NetBSD Operating System by Nathan J. Williams, Wasabi Systems, Inc., presented at FREENIX '02. Solaris threading support The thread support in Solaris is evolving... from Solaris 2 to Solaris 8, the default threading library used an M:N model, but Solaris 9 defaults to 1:1 model thread support. See Sun's multithreaded programming guide and Sun's note about Java and Solaris threading. Java threading support in JDK 1.3.x and earlier As is well known, Java up to JDK1.3.x did not support any method of handling network connections other than one thread per client. Volanomark is a good microbenchmark which measures throughput in messsages per second at various numbers of simultaneous connections. As of May 2003, JDK 1.3 implementations from various vendors are in fact able to handle ten thousand simultaneous connections -- albeit with significant performance degradation. See Table 4 for an idea of which JVMs can handle 10000 connections, and how performance suffers as the number of connections increases. Note: 1:1 threading vs. M:N threading There is a choice when implementing a threading library: you can either put all the threading support in the kernel (this is called the 1:1 threading model), or you can move a fair bit of it into userspace (this is called the M:N threading model). At one point, M:N was thought to be higher performance, but it's so complex that it's hard to get right, and most people are moving away from it. * Why Ingo Molnar prefers 1:1 over M:N * Sun is moving to 1:1 threads * NGPT is an M:N threading library for Linux. * Although Ulrich Drepper planned to use M:N threads in the new glibc threading library, he has since switched to the 1:1 threading model. * MacOSX appears to use 1:1 threading. * FreeBSD and NetBSD appear to still believe in M:N threading... The lone holdouts? Looks like freebsd 7.0 might switch to 1:1 threading (see above), so perhaps M:N threading's believers have finally been proven wrong everywhere. 5. Build the server code into the kernel Novell and Microsoft are both said to have done this at various times, at least one NFS implementation does this, khttpd does this for Linux and static web pages, and "TUX" (Threaded linUX webserver) is a blindingly fast and flexible kernel-space HTTP server by Ingo Molnar for Linux. Ingo's September 1, 2000 announcement says an alpha version of TUX can be downloaded from ftp://ftp.redhat.com/pub/redhat/tux, and explains how to join a mailing list for more info. The linux-kernel list has been discussing the pros and cons of this approach, and the consensus seems to be instead of moving web servers into the kernel, the kernel should have the smallest possible hooks added to improve web server performance. That way, other kinds of servers can benefit. See e.g. Zach Brown's remarks about userland vs. kernel http servers. It appears that the 2.4 linux kernel provides sufficient power to user programs, as the X15 server runs about as fast as Tux, but doesn't use any kernel modifications. Comments Richard Gooch has written a paper discussing I/O options. In 2001, Tim Brecht and MMichal Ostrowski measured various strategies for simple select-based servers. Their data is worth a look. In 2003, Tim Brecht posted source code for userver, a small web server put together from several servers written by Abhishek Chandra, David Mosberger, David Pariag, and Michal Ostrowski. It can use select(), poll(), epoll(), or sigio. Back in March 1999, Dean Gaudet posted: I keep getting asked "why don't you guys use a select/event based model like Zeus? It's clearly the fastest." ... His reasons boiled down to "it's really hard, and the payoff isn't clear". Within a few months, though, it became clear that people were willing to work on it. Mark Russinovich wrote an editorial and an article discussing I/O strategy issues in the 2.2 Linux kernel. Worth reading, even he seems misinformed on some points. In particular, he seems to think that Linux 2.2's asynchronous I/O (see F_SETSIG above) doesn't notify the user process when data is ready, only when new connections arrive. This seems like a bizarre misunderstanding. See also comments on an earlier draft, Ingo Molnar's rebuttal of 30 April 1999, Russinovich's comments of 2 May 1999, a rebuttal from Alan Cox, and various posts to linux-kernel. I suspect he was trying to say that Linux doesn't support asynchronous disk I/O, which used to be true, but now that SGI has implemented KAIO, it's not so true anymore. See these pages at sysinternals.com and MSDN for information on "completion ports", which he said were unique to NT; in a nutshell, win32's "overlapped I/O" turned out to be too low level to be convenient, and a "completion port" is a wrapper that provides a queue of completion events, plus scheduling magic that tries to keep the number of running threads constant by allowing more threads to pick up completion events if other threads that had picked up completion events from this port are sleeping (perhaps doing blocking I/O). See also OS/400's support for I/O completion ports. There was an interesting discussion on linux-kernel in September 1999 titled "> 15,000 Simultaneous Connections" (and the second week of the thread). Highlights: * Ed Hall posted a few notes on his experiences; he's achieved >1000 connects/second on a UP P2/333 running Solaris. His code used a small pool of threads (1 or 2 per CPU) each managing a large number of clients using "an event-based model". * Mike Jagdis posted an analysis of poll/select overhead, and said "The current select/poll implementation can be improved significantly, especially in the blocking case, but the overhead will still increase with the number of descriptors because select/poll does not, and cannot, remember what descriptors are interesting. This would be easy to fix with a new API. Suggestions are welcome..." * Mike posted about his work on improving select() and poll(). * Mike posted a bit about a possible API to replace poll()/select(): "How about a 'device like' API where you write 'pollfd like' structs, the 'device' listens for events and delivers 'pollfd like' structs representing them when you read it? ... " * Rogier Wolff suggested using "the API that the digital guys suggested", http://www.cs.rice.edu/~gaurav/papers/usenix99.ps * Joerg Pommnitz pointed out that any new API along these lines should be able to wait for not just file descriptor events, but also signals and maybe SYSV-IPC. Our synchronization primitives should certainly be able to do what Win32's WaitForMultipleObjects can, at least. * Stephen Tweedie asserted that the combination of F_SETSIG, queued realtime signals, and sigwaitinfo() was a superset of the API proposed in http://www.cs.rice.edu/~gaurav/papers/usenix99.ps. He also mentions that you keep the signal blocked at all times if you're interested in performance; instead of the signal being delivered asynchronously, the process grabs the next one from the queue with sigwaitinfo(). * Jayson Nordwick compared completion ports with the F_SETSIG synchronous event model, and concluded they're pretty similar. * Alan Cox noted that an older rev of SCT's SIGIO patch is included in 2.3.18ac. * Jordan Mendelson posted some example code showing how to use F_SETSIG. * Stephen C. Tweedie continued the comparison of completion ports and F_SETSIG, and noted: "With a signal dequeuing mechanism, your application is going to get signals destined for various library components if libraries are using the same mechanism," but the library can set up its own signal handler, so this shouldn't affect the program (much). * Doug Royer noted that he'd gotten 100,000 connections on Solaris 2.6 while he was working on the Sun calendar server. Others chimed in with estimates of how much RAM that would require on Linux, and what bottlenecks would be hit. Interesting reading! Limits on open filehandles * Any Unix: the limits set by ulimit or setrlimit. * Solaris: see the Solaris FAQ, question 3.46 (or thereabouts; they renumber the questions periodically). * FreeBSD: Edit /boot/loader.conf, add the line set kern.maxfiles=XXXX where XXXX is the desired system limit on file descriptors, and reboot. Thanks to an anonymous reader, who wrote in to say he'd achieved far more than 10000 connections on FreeBSD 4.3, and says "FWIW: You can't actually tune the maximum number of connections in FreeBSD trivially, via sysctl.... You have to do it in the /boot/loader.conf file. The reason for this is that the zalloci() calls for initializing the sockets and tcpcb structures zones occurs very early in system startup, in order that the zone be both type stable and that it be swappable. You will also need to set the number of mbufs much higher, since you will (on an unmodified kernel) chew up one mbuf per connection for tcptempl structures, which are used to implement keepalive." Another reader says "As of FreeBSD 4.4, the tcptempl structure is no longer allocated; you no longer have to worry about one mbuf being chewed up per connection." See also: o the FreeBSD handbook o SYSCTL TUNING, LOADER TUNABLES, and KERNEL CONFIG TUNING in 'man tuning' o The Effects of Tuning a FreeBSD 4.3 Box for High Performance, Daemon News, Aug 2001 o postfix.org tuning notes, covering FreeBSD 4.2 and 4.4 o the Measurement Factory's notes, circa FreeBSD 4.3 * OpenBSD: A reader says "In OpenBSD, an additional tweak is required to increase the number of open filehandles available per process: the openfiles-cur parameter in /etc/login.conf needs to be increased. You can change kern.maxfiles either with sysctl -w or in sysctl.conf but it has no effect. This matters because as shipped, the login.conf limits are a quite low 64 for nonprivileged processes, 128 for privileged." * Linux: See Bodo Bauer's /proc documentation. On 2.4 kernels: echo 32768 > /proc/sys/fs/file-max increases the system limit on open files, and ulimit -n 32768 increases the current process' limit. On 2.2.x kernels, echo 32768 > /proc/sys/fs/file-max echo 65536 > /proc/sys/fs/inode-max increases the system limit on open files, and ulimit -n 32768 increases the current process' limit. I verified that a process on Red Hat 6.0 (2.2.5 or so plus patches) can open at least 31000 file descriptors this way. Another fellow has verified that a process on 2.2.12 can open at least 90000 file descriptors this way (with appropriate limits). The upper bound seems to be available memory. Stephen C. Tweedie posted about how to set ulimit limits globally or per-user at boot time using initscript and pam_limit. In older 2.2 kernels, though, the number of open files per process is still limited to 1024, even with the above changes. See also Oskar's 1998 post, which talks about the per-process and system-wide limits on file descriptors in the 2.0.36 kernel. Limits on threads On any architecture, you may need to reduce the amount of stack space allocated for each thread to avoid running out of virtual memory. You can set this at runtime with pthread_attr_init() if you're using pthreads. * Solaris: it supports as many threads as will fit in memory, I hear. * Linux 2.6 kernels with NPTL: /proc/sys/vm/max_map_count may need to be increased to go above 32000 or so threads. (You'll need to use very small stack threads to get anywhere near that number of threads, though, unless you're on a 64 bit processor.) See the NPTL mailing list, e.g. the thread with subject "Cannot create more than 32K threads?", for more info. * Linux 2.4: /proc/sys/kernel/threads-max is the max number of threads; it defaults to 2047 on my Red Hat 8 system. You can set increase this as usual by echoing new values into that file, e.g. "echo 4000 > /proc/sys/kernel/threads-max" * Linux 2.2: Even the 2.2.13 kernel limits the number of threads, at least on Intel. I don't know what the limits are on other architectures. Mingo posted a patch for 2.1.131 on Intel that removed this limit. It appears to be integrated into 2.3.20. See also Volano's detailed instructions for raising file, thread, and FD_SET limits in the 2.2 kernel. Wow. This document steps you through a lot of stuff that would be hard to figure out yourself, but is somewhat dated. * Java: See Volano's detailed benchmark info, plus their info on how to tune various systems to handle lots of threads. Java issues Up through JDK 1.3, Java's standard networking libraries mostly offered the one-thread-per-client model. There was a way to do nonblocking reads, but no way to do nonblocking writes. In May 2001, JDK 1.4 introduced the package java.nio to provide full support for nonblocking I/O (and some other goodies). See the release notes for some caveats. Try it out and give Sun feedback! HP's java also includes a Thread Polling API. In 2000, Matt Welsh implemented nonblocking sockets for Java; his performance benchmarks show that they have advantages over blocking sockets in servers handling many (up to 10000) connections. His class library is called java-nbio; it's part of the Sandstorm project. Benchmarks showing performance with 10000 connections are available. See also Dean Gaudet's essay on the subject of Java, network I/O, and threads, and the paper by Matt Welsh on events vs. worker threads. Before NIO, there were several proposals for improving Java's networking APIs: * Matt Welsh's Jaguar system proposes preserialized objects, new Java bytecodes, and memory management changes to allow the use of asynchronous I/O with Java. * Interfacing Java to the Virtual Interface Architecture, by C-C. Chang and T. von Eicken, proposes memory management changes to allow the use of asynchronous I/O with Java. * JSR-51 was the Sun project that came up with the java.nio package. Matt Welsh participated (who says Sun doesn't listen?). Other tips * Zero-Copy Normally, data gets copied many times on its way from here to there. Any scheme that eliminates these copies to the bare physical minimum is called "zero-copy". o Thomas Ogrisegg's zero-copy send patch for mmaped files under Linux 2.4.17-2.4.20. Claims it's faster than sendfile(). o IO-Lite is a proposal for a set of I/O primitives that gets rid of the need for many copies. o Alan Cox noted that zero-copy is sometimes not worth the trouble back in 1999. (He did like sendfile(), though.) o Ingo implemented a form of zero-copy TCP in the 2.4 kernel for TUX 1.0 in July 2000, and says he'll make it available to userspace soon. o Drew Gallatin and Robert Picco have added some zero-copy features to FreeBSD; the idea seems to be that if you call write() or read() on a socket, the pointer is page-aligned, and the amount of data transferred is at least a page, *and* you don't immediately reuse the buffer, memory management tricks will be used to avoid copies. But see followups to this message on linux-kernel for people's misgivings about the speed of those memory management tricks. According to a note from Noriyuki Soda: Sending side zero-copy is supported since NetBSD-1.6 release by specifying "SOSEND_LOAN" kernel option. This option is now default on NetBSD-current (you can disable this feature by specifying "SOSEND_NO_LOAN" in the kernel option on NetBSD_current). With this feature, zero-copy is automatically enabled, if data more than 4096 bytes are specified as data to be sent. o The sendfile() system call can implement zero-copy networking. The sendfile() function in Linux and FreeBSD lets you tell the kernel to send part or all of a file. This lets the OS do it as efficiently as possible. It can be used equally well in servers using threads or servers using nonblocking I/O. (In Linux, it's poorly documented at the moment; use _syscall4 to call it. Andi Kleen is writing new man pages that cover this. See also Exploring The sendfile System Call by Jeff Tranter in Linux Gazette issue 91.) Rumor has it, ftp.cdrom.com benefitted noticeably from sendfile(). A zero-copy implementation of sendfile() is on its way for the 2.4 kernel. See LWN Jan 25 2001. One developer using sendfile() with Freebsd reports that using POLLWRBAND instead of POLLOUT makes a big difference. Solaris 8 (as of the July 2001 update) has a new system call 'sendfilev'. A copy of the man page is here.. The Solaris 8 7/01 release notes also mention it. I suspect that this will be most useful when sending to a socket in blocking mode; it'd be a bit of a pain to use with a nonblocking socket. * Avoid small frames by using writev (or TCP_CORK) A new socket option under Linux, TCP_CORK, tells the kernel to avoid sending partial frames, which helps a bit e.g. when there are lots of little write() calls you can't bundle together for some reason. Unsetting the option flushes the buffer. Better to use writev(), though... See LWN Jan 25 2001 for a summary of some very interesting discussions on linux-kernel about TCP_CORK and a possible alternative MSG_MORE. * Behave sensibly on overload. [Provos, Lever, and Tweedie 2000] notes that dropping incoming connections when the server is overloaded improved the shape of the performance curve, and reduced the overall error rate. They used a smoothed version of "number of clients with I/O ready" as a measure of overload. This technique should be easily applicable to servers written with select, poll, or any system call that returns a count of readiness events per call (e.g. /dev/poll or sigtimedwait4()). * Some programs can benefit from using non-Posix threads. Not all threads are created equal. The clone() function in Linux (and its friends in other operating systems) lets you create a thread that has its own current working directory, for instance, which can be very helpful when implementing an ftp server. See Hoser FTPd for an example of the use of native threads rather than pthreads. * Caching your own data can sometimes be a win. "Re: fix for hybrid server problems" by Vivek Sadananda Pai (vivek@cs.rice.edu) on new-httpd, May 9th, states: "I've compared the raw performance of a select-based server with a multiple-process server on both FreeBSD and Solaris/x86. On microbenchmarks, there's only a marginal difference in performance stemming from the software architecture. The big performance win for select-based servers stems from doing application-level caching. While multiple-process servers can do it at a higher cost, it's harder to get the same benefits on real workloads (vs microbenchmarks). I'll be presenting those measurements as part of a paper that'll appear at the next Usenix conference. If you've got postscript, the paper is available at http://www.cs.rice.edu/~vivek/flash99/" Other limits * Old system libraries might use 16 bit variables to hold file handles, which causes trouble above 32767 handles. glibc2.1 should be ok. * Many systems use 16 bit variables to hold process or thread id's. It would be interesting to port the Volano scalability benchmark to C, and see what the upper limit on number of threads is for the various operating systems. * Too much thread-local memory is preallocated by some operating systems; if each thread gets 1MB, and total VM space is 2GB, that creates an upper limit of 2000 threads. * Look at the performance comparison graph at the bottom of http://www.acme.com/software/thttpd/benchmarks.html. Notice how various servers have trouble above 128 connections, even on Solaris 2.6? Anyone who figures out why, let me know. Note: if the TCP stack has a bug that causes a short (200ms) delay at SYN or FIN time, as Linux 2.2.0-2.2.6 had, and the OS or http daemon has a hard limit on the number of connections open, you would expect exactly this behavior. There may be other causes. Kernel Issues For Linux, it looks like kernel bottlenecks are being fixed constantly. See Linux Weekly News, Kernel Traffic, the Linux-Kernel mailing list, and my Mindcraft Redux page. In March 1999, Microsoft sponsored a benchmark comparing NT to Linux at serving large numbers of http and smb clients, in which they failed to see good results from Linux. See also my article on Mindcraft's April 1999 Benchmarks for more info. See also The Linux Scalability Project. They're doing interesting work, including Niels Provos' hinting poll patch, and some work on the thundering herd problem. See also Mike Jagdis' work on improving select() and poll(); here's Mike's post about it. Mohit Aron (aron@cs.rice.edu) writes that rate-based clocking in TCP can improve HTTP response time over 'slow' connections by 80%. Measuring Server Performance Two tests in particular are simple, interesting, and hard: 1. raw connections per second (how many 512 byte files per second can you serve?) 2. total transfer rate on large files with many slow clients (how many 28.8k modem clients can simultaneously download from your server before performance goes to pot?) Jef Poskanzer has published benchmarks comparing many web servers. See http://www.acme.com/software/thttpd/benchmarks.html for his results. I also have a few old notes about comparing thttpd to Apache that may be of interest to beginners. Chuck Lever keeps reminding us about Banga and Druschel's paper on web server benchmarking. It's worth a read. IBM has an excellent paper titled Java server benchmarks [Baylor et al, 2000]. It's worth a read. Examples Interesting select()-based servers * thttpd Very simple. Uses a single process. It has good performance, but doesn't scale with the number of CPU's. Can also use kqueue. * mathopd. Similar to thttpd. * fhttpd * boa * Roxen * Zeus, a commercial server that tries to be the absolute fastest. See their tuning guide. * The other non-Java servers listed at http://www.acme.com/software/thttpd/benchmarks.html * BetaFTPd * Flash-Lite - web server using IO-Lite. * Flash: An efficient and portable Web server -- uses select(), mmap(), mincore() * The Flash web server as of 2003 -- uses select(), modified sendfile(), async open() * xitami - uses select() to implement its own thread abstraction for portability to systems without threads. * Medusa - a server-writing toolkit in Python that tries to deliver very high performance. * userver - a small http server that can use select, poll, epoll, or sigio Interesting /dev/poll-based servers * N. Provos, C. Lever, "Scalable Network I/O in Linux," May, 2000. [FREENIX track, Proc. USENIX 2000, San Diego, California (June, 2000).] Describes a version of thttpd modified to support /dev/poll. Performance is compared with phhttpd. Interesting kqueue()-based servers * thttpd (as of version 2.21?) * Adrian Chadd says "I'm doing a lot of work to make squid actually LIKE a kqueue IO system"; it's an official Squid subproject; see http://squid.sourceforge.net/projects.html#commloops. (This is apparently newer than Benno's patch.) Interesting realtime signal-based servers * Chromium's X15. This uses the 2.4 kernel's SIGIO feature together with sendfile() and TCP_CORK, and reportedly achieves higher speed than even TUX. The source is available under a community source (not open source) license. See the original announcement by Fabio Riccardi. * Zach Brown's phhttpd - "a quick web server that was written to showcase the sigio/siginfo event model. consider this code highly experimental and yourself highly mental if you try and use it in a production environment." Uses the siginfo features of 2.3.21 or later, and includes the needed patches for earlier kernels. Rumored to be even faster than khttpd. See his post of 31 May 1999 for some notes. Interesting thread-based servers * Hoser FTPD. See their benchmark page. * Peter Eriksson's phttpd and * pftpd * The Java-based servers listed at http://www.acme.com/software/thttpd/benchmarks.html * Sun's Java Web Server (which has been reported to handle 500 simultaneous clients) Interesting in-kernel servers * khttpd * "TUX" (Threaded linUX webserver) by Ingo Molnar et al. For 2.4 kernel. Other interesting links * Jeff Darcy's notes on high-performance server design * Ericsson's ARIES project -- benchmark results for Apache 1 vs. Apache 2 vs. Tomcat on 1 to 12 processors * Prof. Peter Ladkin's Web Server Performance page. * Novell's FastCache -- claims 10000 hits per second. Quite the pretty performance graph. * Rik van Riel's Linux Performance Tuning site Changelog $Log: c10k.html,v $ Revision 1.212 2006/09/02 14:52:13 dank added asio Revision 1.211 2006/07/27 10:28:58 dank Link to Cal Henderson's book. Revision 1.210 2006/07/27 10:18:58 dank Listify polyakov links, add Drepper's new proposal, note that FreeBSD 7 might move to 1:1 Revision 1.209 2006/07/13 15:07:03 dank link to Scale! library, updated Polyakov links Revision 1.208 2006/07/13 14:50:29 dank Link to Polyakov's patches Revision 1.207 2003/11/03 08:09:39 dank Link to Linus's message deprecating the idea of aio_open Revision 1.206 2003/11/03 07:44:34 dank link to userver Revision 1.205 2003/11/03 06:55:26 dank Link to Vivek Pei's new Flash paper, mention great specweb99 score Copyright 1999-2006 Dan Kegel dank@kegel.com Last updated: 2 Sept 2006 [Return to www.kegel.com] The C10K problem 编写连接数巨大的高负载服务器程序时，经典的多线程模式和select模式都不再适用。应当抛弃它们，采用epoll/kqueue /dev_poll来捕获I/O事件。最后简要介绍了AIO。 网络服务在处理数以万计的客户端连接时，往往出现效率低下甚至完全瘫痪，这被称为 C10K问题。随着互联网的迅速发展，越来越多的网络服务开始面临C10K问题，作为大型 网站的开发人员有必要对C10K问题有一定的了解。本文的主要参考文献是 http://www.kegel.com/c10k.html。 C10K问题的最大特点是：设计不够良好的程序，其性能和连接数及机器性能的关系往往 是非线性的。举个例子：如果没有考虑过C10K问题，一个经典的基于select的程序能在 旧服务器上很好处理1000并发的吞吐量，它在2倍性能新服务器上往往处理不了并发2000的吞吐量。 这是因为在策略不当时，大量操作的消耗和当前连接数n成线性相关。会导致单个任务的资源消耗和当前连接数的关系会是O(n)。而服务程序需要同时对数以万计的socket进 行I/O处理，积累下来的资源消耗会相当可观，这显然会导致系统吞吐量不能和机器性 能匹配。为解决这个问题，必须改变对连接提供服务的策略。 主要有两方面的策略：1.应用软件以何种方式和操作系统合作，获取I/O事件并调度多 个socket上的I/O操作；2. 应用软件以何种方式处理任务和线程/进程的关系。前者主 要有阻塞I/O、非阻塞I/O、异步I/O这3种方案，后者主要有每任务1进程、每任务1线 程、单线程、多任务共享线程池以及一些更复杂的变种方案。常用的经典策略如下： 1. Serve one client with each thread/process, and use blocking I/O 这是小程序和java常用的策略，对于交互式的长连接应用也是常见的选择(比如BBS)。 这种策略很能难足高性能程序的需求，好处是实现极其简单，容易嵌入复杂的交互逻 辑。Apache、ftpd等都是这种工作模式。 2. Serve many clients with single thread, and use nonblocking I/O and readiness notification 这是经典模型，datapipe等程序都是如此实现的。优点在于实现较简单，方便移植，也 能提供足够的性能；缺点在于无法充分利用多CPU的机器。尤其是程序本身没有复杂的 业务逻辑时。 3. Serve many clients with each thread, and use nonblocking I/O and readiness notification 对经典模型2的简单改进，缺点是容易在多线程并发上出bug，甚至某些OS不支持多线程 操作readiness notification。 4. Serve many clients with each thread, and use asynchronous I/O 在有AI/O支持的OS上，能提供相当高的性能。不过AI/O编程模型和经典模型差别相当 大，基本上很难写出一个框架同时支持AI/O和经典模型，降低了程序的可移植性。在 Windows上，这基本上是唯一的可选方案。 本文主要讨论模型2的细节，也就是在模型2下应用软件如何处理Socket I/O。 select 与 poll 最原始的同步阻塞 I/O 模型的典型流程如下： 同步阻塞 I/O 模型的典型流程 从应用程序的角度来说，read 调用会延续很长时间，应用程序需要相当多线程来解决 并发访问问题。同步非阻塞I/O对此有所改进： 经典的单线程服务器程序结构往往如下： C代码 1. do { 2. Get Readiness Notification of all sockets 3. Dispatch ready handles to corresponding handlers 4. If (readable) { 5. read the socket 6. If (read done) 7. Handler process the request 8. } 9. if (writable) 10. write response 11. if (nothing to do) 12. close socket 13. } while(True) do { Get Readiness Notification of all sockets Dispatch ready handles to corresponding handlers If (readable) { read the socket If (read done) Handler process the request } if (writable) write response if (nothing to do) close socket } while(True) 异步阻塞 I/O 模型的典型流程 其中关键的部分是readiness notification，找出哪一个socket上面发生了I/O事件。 一般从教科书和例子程序中首先学到的是用select来实现。Select定义如下： int select(int n, fd_set *rd_fds, fd_set *wr_fds, fd_set *ex_fds, struct timeval *timeout); Select用到了fd_set结构，从man page里可以知道fd_set能容纳的句柄和FD_SETSIZE相 关。实际上fd_set在*nix下是一个bit标志数组，每个bit表示对应下标的fd是不是在 fd_set中。fd_set只能容纳编号小于 FD_SETSIZE的那些句柄。 FD_SETSIZE默认是1024，如果向fd_set里放入过大的句柄，数组越界以后程序就会垮 掉。系统默认限制了一个进程最大的句柄号不超过1024，但是可以通过ulimit -n命令 /setrlimit函数来扩大这一限制。如果不幸一个程序在FD_SETSIZE=1024的环境下编 译，运行时又遇到ulimit –n > 1024的，那就只有祈求上帝保佑不会垮掉了。 在ACE环境中，ACE_Select_Reactor针对这一点特别作了保护措施，但是还是有recv_n 这样的函数间接的使用了select，这需要大家注意。 针对fd_set的问题，*nix提供了poll函数作为select的一个替代品。Poll的接口如下： int poll(struct pollfd *ufds, unsigned int nfds, int timeout); 第1个参数ufds是用户提供的一个pollfd数组，数组大小由用户自行决定，因此避免了 FD_SETSIZE带来的麻烦。Ufds是fd_set的一个完全替代品，从select到poll的移植很方 便。到此为止，至少我们面对C10K，可以写出一个能work的程序了。 然而Select和Poll在连接数增加时，性能急剧下降。这有两方面的原因：首先操作系统 面对每次的select/poll操作，都需要重新建立一个当前线程的关心事件列表，并把线 程挂在这个复杂的等待队列上，这是相当耗时的。其次，应用软件在select/poll返回 后也需要对传入的句柄列表做一次扫描来dispatch，这也是很耗时的。这两件事都是和 并发数相关，而I/O事件的密度也和并发数相关，导致CPU占用率和并发数近似成O(n2)的关系。 epoll, kqueue, /dev/poll 因为以上的原因，*nix的hacker们开发了epoll, kqueue, /dev/poll这3套利器来帮助 大家，让我们跪拜三分钟来感谢这些大神。其中epoll是linux的方案，kqueue是 freebsd的方案，/dev/poll是最古老的Solaris的方案，使用难度依次递增。 简单的说，这些api做了两件事：1.避免了每次调用select/poll时kernel分析参数建立 事件等待结构的开销，kernel维护一个长期的事件关注列表，应用程序通过句柄修改这 个列表和捕获I/O事件。2.避免了select/poll返回后，应用程序扫描整个句柄表的开 销，Kernel直接返回具体的事件列表给应用程序。 在接触具体api之前，先了解一下边缘触发(edge trigger)和条件触发(level trigger) 的概念。边缘触发是指每当状态变化时发生一个io事件，条件触发是只要满足条件就发 生一个io事件。举个读socket的例子，假定经过长时间的沉默后，现在来了100个字 节，这时无论边缘触发和条件触发都会产生一个read ready notification通知应用程 序可读。应用程序读了50个字节，然后重新调用api等待io事件。这时条件触发的api会 因为还有50个字节可读从而立即返回用户一个read ready notification。而边缘触发 的api会因为可读这个状态没有发生变化而陷入长期等待。 因此在使用边缘触发的api时，要注意每次都要读到socket返回EWOULDBLOCK为止，否则 这个socket就算废了。而使用条件触发的api时，如果应用程序不需要写就不要关注 socket可写的事件，否则就会无限次的立即返回一个write ready notification。大家 常用的select就是属于条件触发这一类，以前本人就犯过长期关注socket写事件从而CPU 100%的毛病。 epoll的相关调用如下： C代码 1. int epoll_create(int size) 2. int epoll_ctl(int epfd, int op, int fd, struct epoll_event *event) 3. int epoll_wait(int epfd, struct epoll_event * events, int maxevents, int timeout) int epoll_create(int size) int epoll_ctl(int epfd, int op, int fd, struct epoll_event *event) int epoll_wait(int epfd, struct epoll_event * events, int maxevents, int timeout) epoll_create创建kernel中的关注事件表，相当于创建fd_set。 epoll_ctl修改这个表，相当于FD_SET等操作 epoll_wait等待I/O事件发生，相当于select/poll函数 epoll完全是select/poll的升级版，支持的事件完全一致。并且epoll同时支持边缘触 发和条件触发，一般来讲边缘触发的性能要好一些。这里有个简单的例子： C代码 1. struct epoll_event ev, *events; 2. int kdpfd = epoll_create(100); 3. ev.events = EPOLLIN | EPOLLET; // 注意这个EPOLLET，指定了边缘触发 4. ev.data.fd =listener; 5. epoll_ctl(kdpfd, EPOLL_CTL_ADD, listener, &ev); 6. for(;;) { 7. nfds = epoll_wait(kdpfd, events, maxevents, -1); 8. for(n = 0; n < nfds; ++n) { 9. if(events[n].data.fd == listener) { 10. client = accept(listener, (struct sockaddr *) &local, 11. &addrlen); 12. if(client < 0){ 13. perror("accept"); 14. continue; 15. } 16. setnonblocking(client); 17. ev.events = EPOLLIN | EPOLLET; 18. ev.data.fd = client; 19. if (epoll_ctl(kdpfd, EPOLL_CTL_ADD, client, &ev) < 0) { 20. fprintf(stderr, "epoll set insertion error: fd=%d0, 21. client); 22. return -1; 23. } 24. } 25. else 26. do_use_fd(events[n].data.fd); 27. } 28. } struct epoll_event ev, *events; int kdpfd = epoll_create(100); ev.events = EPOLLIN | EPOLLET; // 注意这个EPOLLET，指定了边缘触发 ev.data.fd =listener; epoll_ctl(kdpfd, EPOLL_CTL_ADD, listener, &ev); for(;;) { nfds = epoll_wait(kdpfd, events, maxevents, -1); for(n = 0; n < nfds; ++n) { if(events[n].data.fd == listener) { client = accept(listener, (struct sockaddr *) &local, &addrlen); if(client < 0){ perror("accept"); continue; } setnonblocking(client); ev.events = EPOLLIN | EPOLLET; ev.data.fd = client; if (epoll_ctl(kdpfd, EPOLL_CTL_ADD, client, &ev) < 0) { fprintf(stderr, "epoll set insertion error: fd=%d0, client); return -1; } } else do_use_fd(events[n].data.fd); } } 简单介绍一下kqueue和/dev/poll kqueue是freebsd的宠儿，kqueue实际上是一个功能相当丰富的kernel事件队列，它不 仅仅是select/poll的升级，而且可以处理signal、目录结构变化、进程等多种事件。 Kqueue是边缘触发的 /dev/poll是Solaris的产物，是这一系列高性能API中最早出现的。Kernel提供一个特 殊的设备文件/dev/poll。应用程序打开这个文件得到操纵fd_set的句柄，通过写入pollfd来修改它，一个特殊ioctl调用用来替换 select。由于出现的年代比较早，所以 /dev/poll的接口现在看上去比较笨拙可笑。C++开发：ACE 5.5以上版本提供了ACE_Dev_Poll_Reactor封装了epoll和/dev/poll两种 api，需要分别在config.h中定义ACE_HAS_EPOLL和ACE_HAS_DEV_POLL来启用。 Java开发： JDK 1.6的Selector提供了对epoll的支持，JDK1.4提供了对/dev/poll的支 持。只要选择足够高的JDK版本就行了。 异步I/O以及Windows和经典模型不同，异步I/O提供了另一种思路。和传统的同步I/O不同，异步I/O允许进程发起很多 I/O 操作，而不用阻塞或等待任何操作完成。稍后或在接收到 I/O 操作完 成的通知时，进程就可以检索 I/O 操作的结果。 异步非阻塞 I/O 模型是一种处理与 I/O 重叠进行的模型。读请求会立即返回，说明 read 请求已经成功发起了。在后台完成读操作时，应用程序然后会执行其他处理操 作。当 read 的响应到达时，就会产生一个信号或执行一个基于线程的回调函数来完成 这次 I/O 处理过程。异步I/O 模型的典型流程： 异步非阻塞 I/O 模型的典型流程 对于文件操作而言，AIO有一个附带的好处：应用程序将多个细碎的磁盘请求并发的提 交给操作系统后，操作系统有机会对这些请求进行合并和重新排序，这对同步调用而言 是不可能的——除非创建和请求数目同样多的线程。 Linux Kernel 2.6提供了对AIO的有限支持——仅支持文件系统。libc也许能通过来线 程来模拟socket的AIO，不过这对性能没意义。总的来说Linux的aio还不成熟 Windows对AIO的支持很好，有IOCP队列和IPCP回调两种方式，甚至提供了用户级异步调 用APC功能。Windows下AIO是唯一可用的高性能方案，详情请参考MSDN。

                   4. Try Lock-free Logic/Algorithm/DataStructure

             3. Using FP

                1. e.g. Erlang OTP

      4. Improving Algorithm

         1. Changing Algorithms to Get a Less BigO

            1. "Less BigO" doesn't necessarily mean "less time"

            2. KISS

         2. Imporving constant (BigOO)

            1. e.g. Use sentry in double-list

         3. Dealing with Omega & BigO

         4. Introducing Amortized Analysis

         5. Finding Better Substitute of Data Structures

         6. Parallelism Algorithm

         7. NP Hard?

            1. Quantum computer! :)

      5. Tricks

         1. Compiler Optimization

            1. Using Compiler/PerformanceLib from CPU Vendor

            2. Proebsting's Law

               http://research.microsoft.com/en-us/um/people/toddpro/papers/law.htm Proebsting's Law: Compiler Advances Double Computing Power Every 18 Years I claim the following simple experiment supports this depressing claim. Run your favorite set of benchmarks with your favorite state-of-the-art optimizing compiler. Run the benchmarks both with and without optimizations enabled. The ratio of of those numbers represents the entirety of the contribution of compiler optimizations to speeding up those benchmarks. Let's assume that this ratio is about 4X for typical real-world applications, and let's further assume that compiler optimization work has been going on for about 36 years. These assumptions lead to the conclusion that compiler optimization advances double computing power every 18 years. QED. This means that while hardware computing horsepower increases at roughly 60%/year, compiler optimizations contribute only 4%. Basically, compiler optimization work makes only marginal contributions. Perhaps this means Programming Language Research should be concentrating on something other than optimizations. Perhaps programmer productivity is a more fruitful arena.

         2. Changing Tree Recursion to Tail Recursion, or Iteration

         3. Using Lazy Evaluation

            1. Copy On Write (COW)

         4. Avoiding Copying

            1. Return Value Optimization (RVO)

         5. Interpreter/VM

            1. Compiling to Bytecode/Native code

               1. e.g. PYC/HipHop

            2. Hybrid

               1. e.g. C module in Python

            3. Binary Optimizer

            4. JIT

               1. e.g. BitBlt/JVM's JIT

         6. Better packing for modules

            1. e.g. reorganizing DLL/so

3. Hardware

   1. The most important concept: Order of an operation

   2. Cache

      1. Type

         1. Instruction Cache

            1. Trace Cache

               One of the more extreme examples of cache specialization is the trace cache found in the Intel Pentium 4 microprocessors. A trace cache is a mechanism for increasing the instruction fetch bandwidth and decreasing power consumption (in the case of the Pentium 4) by storing traces of instructions that have already been fetched and decoded. The earliest widely acknowledged academic publication of trace cache was by Eric Rotenberg, Steve Bennett, and Jim Smith in their 1996 paper "Trace Cache: a Low Latency Approach to High Bandwidth Instruction Fetching."

         2. Data Cache

            1. Associativity

               1. Set Associative

                  1. Cache Capacity

                  2. Ways

                  3. Line Size (Block Size), in bytes

               2. Fully Associative

               3. Direct Mapping

               4. Victim Cache

                  1. Using Dead Blocks as a Virtual Victim Cache

                     Using Dead Blocks as a Virtual Victim Cache, the paper: http://www.cs.utah.edu/cmpmsi/papers10/paper3.pdf

      2. Level

         1. L1/L2/L3

            1. Inclusive

               1. Non-strictly Inclusive

            2. Exclusive

      3. Update Policy

         1. Writeback

         2. Writethrough

      4. Cache vs Buffer

      5. Cache everywhere (the spirit)

   3. CPU

      1. Real Mode & Protected Mode

      2. Endian

         1. Big

         2. Little

         3. Supported Both

   4. Virtual Memory

      1. Page & Segment

   5. Parallel vs Serialization

      1. Differential Signals

         1. LVDS

   6. Virtualization

      1. Concepts

         1. ISA

            1. Virtual ISA

               1. Stack Based Lang

            2. Extension to x86 ISA

            3. Co-designed ISA

         2. API & ABI

      2. Implementation

         1. Interpretation

            1. Dispatching by Loop vs Threaded Code

         2. 子主题 2

      3. Type

         1. Process VM

            1. Same ISA

               1. Dynamic Binary Optimization

               2. Multiprogramming

            2. Different ISA

               1. Dynamic Binary Translator

               2. HLL VM (High Level Language VM)

                  1. Virtual ISA

         2. System VM

            1. Same ISA

               1. Native VM

               2. Hosted VM

            2. Different ISA

               1. Whole System VM

               2. Co-designed System VM

4. Algorithm

   1. Stack

      1. Expression Evaluation

      2. Recursion To Iteration

      3. Use Stack simulating queue

   2. Queue

   3. Array

      1. Static Array

      2. Dynamic Array

         1. Single Buffer

         2. Multi-buffer (Linked)

   4. List

      1. CONS

      2. Double linked list with sentry

      3. Loop Detection

         1. Find the 1st element in loop (the one with two predecessors)

   5. Tree

      1. Binary Tree

      2. BTrees

      3. R-B Tree

      4. BSP Tree

         1. k-d Tree

            1. 3-d Tree

      5. Trie

         1. PATRICIA (radix tree)

      6. Ternary Search Tree (TST)

         1. Partial Match Search

         2. Near Neighbour Search

      7. Suffix Tree

         1. Suffix Array

            1. DC3

            2. MF

      8. Tournament Tree

         1. Winner Tree

         2. Loser Tree

   6. Heap

      1. Priority Queue

   7. Graph

      1. DAG

         1. Strongly Connected Component & DAG

      2. DFS

      3. BFS

         1. Shortest Path

      4. To Be Updated...

   8. String

      1. Searching Algorithm

         1. Brute Force

         2. KMP

         3. BM

         4. Sunday

         5. Suffix Array/Tree

      2. Hamming Distance

      3. LCS

         longest common subsequence http://en.wikipedia.org/wiki/Longest_common_subsequence_problem

   9. Other

      1. Hash Map

         1. Collision

            1. Linked List

               1. MRU

            2. Rehash

               1. Fake Deletion

                  We don't break the search chain when deleting an object in it.

         2. Multi Hash

            1. Bloom Filter

         3. TST is a better Hash

      2. Searching

         1. Binary Search

         2. AVL Search

         3. R-B Tree Search

   10. Sorting

       1. Serial Sorting Algorithms

          1. Bubble Sort

          2. Insert Sort

          3. Selection Sort

          4. Radix Sort

          5. Quick Sort

             1. Handle O(N*N), Assure N*lg(N)

          6. Heap Sort

          7. Shell Sort

       2. Sorting Network

          1. Comparison Network

   11. Selection

       1. Bubble Selection

       2. Quick Selection

       3. Tournament Tree Selection

   12. Type

       1. Greedy

       2. Divide & Conquer

       3. Dynamic Programming

       4. Linear Programming

       5. Randomized

       6. Backtracking

       7. Reduce

   13. Amortized Analysis

       1. Potential

5. Other

   1. regxp

   2. Tools

      1. GNU Tools

         1. emacs

         2. vi

         3. gdb

         4. gcc

   3. Character Encoding

      1. UNICODE

         谈谈Unicode编码 －－简要解释UCS、UTF、BMP、BOM等名词　　作者：fmddlmyy 　　这是一篇程序员写给程序员的趣味读物。所谓趣味是指可以比较轻松地了解一些原来不清楚的概念，增进知识，类似于打RPG游戏的升级。整理这篇文章的动机是两个问题： 问题一： 　　使用Windows记事本的“另存为”，可以在GBK、Unicode、Unicode big endian和UTF-8这几种编码方式间相互转换。同样是txt文件，Windows是怎样识别编码方式的呢？ 　　我很早前就发现Unicode、Unicode big endian和UTF-8编码的txt文件的开头会多出几个字节，分别是FF、FE（Unicode）,FE、FF（Unicode big endian）,EF、BB、BF（UTF-8）。但这些标记是基于什么标准呢？ 问题二： 　　最近在网上看到一个ConvertUTF.c，实现了UTF-32、UTF-16和UTF-8这三种编码方式的相互转换。对于Unicode(UCS2)、GBK、UTF-8这些编码方式，我原来就了解。但这个程序让我有些糊涂，想不起来UTF-16和UCS2有什么关系。 　　查了查相关资料，总算将这些问题弄清楚了，顺带也了解了一些Unicode的细节。作者写成一篇文章，送给有过类似疑问的朋友。本文在写作时尽量做到通俗易懂，但要求读者知道什么是字节，什么是十六进制。 0、big endian和little endian 　　big endian和little endian是CPU处理多字节数的不同方式。例如“汉”字的Unicode编码是6C49。那么写到文件里时，究竟是将6C写在前面，还是将49写在前面？如果将6C写在前面，就是big endian。如果将49写在前面，就是little endian。 　　“endian”这个词出自《格列佛游记》。小人国的内战就源于吃鸡蛋时是究竟从大头(Big-Endian)敲开还是从小头(Little-Endian)敲开，由此曾发生过六次叛乱，一个皇帝送了命，另一个丢了王位。 　　我们一般将endian翻译成“字节序”，将big endian和little endian称作“大尾”和“小尾”。 1、字符编码、内码，顺带介绍汉字编码 　　字符必须编码后才能被计算机处理。计算机使用的缺省编码方式就是计算机的内码。早期的计算机使用7位的ASCII编码，为了处理汉字，程序员设计了用于简体中文的GB2312和用于繁体中文的big5。 　　GB2312(1980年)一共收录了7445个字符，包括6763个汉字和682个其它符号。汉字区的内码范围高字节从B0-F7，低字节从A1-FE，占用的码位是72*94=6768。其中有5个空位是D7FA-D7FE。 　　GB2312支持的汉字太少。1995年的汉字扩展规范GBK1.0收录了21886个符号，它分为汉字区和图形符号区。汉字区包括21003个字符。2000年的GB18030是取代GBK1.0的正式国家标准。该标准收录了27484个汉字，同时还收录了藏文、蒙文、维吾尔文等主要的少数民族文字。现在的PC平台必须支持GB18030，对嵌入式产品暂不作要求。所以手机、MP3一般只支持GB2312。 　　从ASCII、GB2312、GBK到GB18030，这些编码方法是向下兼容的，即同一个字符在这些方案中总是有相同的编码，后面的标准支持更多的字符。在这些编码中，英文和中文可以统一地处理。区分中文编码的方法是高字节的最高位不为0。按照程序员的称呼，GB2312、GBK到GB18030都属于双字节字符集 (DBCS)。 　　有的中文Windows的缺省内码还是GBK，可以通过GB18030升级包升级到GB18030。不过GB18030相对GBK增加的字符，普通人是很难用到的，通常我们还是用GBK指代中文Windows内码。 这里还有一些细节： 　　①GB2312的原文还是区位码，从区位码到内码，需要在高字节和低字节上分别加上A0。 　　②在DBCS中，GB内码的存储格式始终是big endian，即高位在前。 　　③GB2312的两个字节的最高位都是1。但符合这个条件的码位只有128*128=16384个。所以GBK和GB18030的低字节最高位都可能不是1。不过这不影响DBCS字符流的解析：在读取DBCS字符流时，只要遇到高位为1的字节，就可以将下两个字节作为一个双字节编码，而不用管低字节的高位是什么。 2、Unicode、UCS和UTF 　　前面提到从ASCII、GB2312、GBK到GB18030的编码方法是向下兼容的。而Unicode只与ASCII兼容（更准确地说，是与ISO-8859-1兼容），与GB码不兼容。例如“汉”字的Unicode编码是6C49，而GB码是BABA。 　　Unicode也是一种字符编码方法，不过它是由国际组织设计，可以容纳全世界所有语言文字的编码方案。Unicode的学名是"Universal Multiple-Octet Coded Character Set"，简称为UCS。UCS可以看作是"Unicode Character Set"的缩写。 　　根据维基百科全书(http://zh.wikipedia.org/wiki/ )的记载：历史上存在两个试图独立设计Unicode的组织，即国际标准化组织（ISO）和一个软件制造商的协会（unicode.org）。ISO开发了ISO 10646项目，Unicode协会开发了Unicode项目。 　　在1991年前后，双方都认识到世界不需要两个不兼容的字符集。于是它们开始合并双方的工作成果，并为创立一个单一编码表而协同工作。从Unicode2.0开始，Unicode项目采用了与ISO 10646-1相同的字库和字码。 　　目前两个项目仍都存在，并独立地公布各自的标准。Unicode协会现在的最新版本是2005年的Unicode 4.1.0。ISO的最新标准是ISO 10646-3:2003。 　　UCS只是规定如何编码，并没有规定如何传输、保存这个编码。例如“汉”字的UCS编码是6C49，我可以用4个ascii数字来传输、保存这个编码；也可以用utf-8编码:3个连续的字节E6 B1 89来表示它。关键在于通信双方都要认可。UTF-8、UTF-7、UTF-16都是被广泛接受的方案。UTF-8的一个特别的好处是它与ISO-8859-1完全兼容。UTF是“UCS Transformation Format”的缩写。 　　IETF的RFC2781和RFC3629以RFC的一贯风格，清晰、明快又不失严谨地描述了UTF-16和UTF-8的编码方法。我总是记不得IETF是Internet Engineering Task Force的缩写。但IETF负责维护的RFC是Internet上一切规范的基础。 2.1、内码和code page 　　目前Windows的内核已经采用Unicode编码，这样在内核上可以支持全世界所有的语言文字。但是由于现有的大量程序和文档都采用了某种特定语言的编码，例如GBK，Windows不可能不支持现有的编码，而全部改用Unicode。 　　Windows使用代码页(code page)来适应各个国家和地区。code page可以被理解为前面提到的内码。GBK对应的code page是CP936。 　　微软也为GB18030定义了code page：CP54936。但是由于GB18030有一部分4字节编码，而Windows的代码页只支持单字节和双字节编码，所以这个code page是无法真正使用的。 3、UCS-2、UCS-4、BMP 　　UCS有两种格式：UCS-2和UCS-4。顾名思义，UCS-2就是用两个字节编码，UCS-4就是用4个字节（实际上只用了31位，最高位必须为0）编码。下面让我们做一些简单的数学游戏： 　　UCS-2有2^16=65536个码位，UCS-4有2^31=2147483648个码位。 　　UCS-4根据最高位为0的最高字节分成2^7=128个group。每个group再根据次高字节分为256个plane。每个plane根据第3个字节分为256行(rows)，每行包含256个cells。当然同一行的cells只是最后一个字节不同，其余都相同。 　　group 0的plane 0被称作Basic Multilingual Plane, 即BMP。或者说UCS-4中，高两个字节为0的码位被称作BMP。 　　将UCS-4的BMP去掉前面的两个零字节就得到了UCS-2。在UCS-2的两个字节前加上两个零字节，就得到了UCS-4的BMP。而目前的UCS-4规范中还没有任何字符被分配在BMP之外。 4、UTF编码 　　UTF-8就是以8位为单元对UCS进行编码。从UCS-2到UTF-8的编码方式如下： 　　　　　UCS-2编码(16进制)　　　　　　UTF-8 字节流(二进制) 　　　　　0000 - 007F　　　　　　　　　0xxxxxxx 　　　　　0080 - 07FF　　　　　　　　　110xxxxx 10xxxxxx 　　　　　0800 - FFFF　　　　　　　　　1110xxxx 10xxxxxx 10xxxxxx 　　例如“汉”字的Unicode编码是6C49。6C49在0800-FFFF之间，所以肯定要用3字节模板了：1110xxxx 10xxxxxx 10xxxxxx。将6C49写成二进制是：0110 110001 001001， 用这个比特流依次代替模板中的x，得到：11100110 10110001 10001001，即E6 B1 89。 　　读者可以用记事本测试一下我们的编码是否正确。需要注意，UltraEdit在打开utf-8编码的文本文件时会自动转换为UTF-16，可能产生混淆。你可以在设置中关掉这个选项。更好的工具是Hex Workshop。 　　UTF-16以16位为单元对UCS进行编码。对于小于0x10000的UCS码，UTF-16编码就等于UCS码对应的16位无符号整数。对于不小于0x10000的UCS码，定义了一个算法。不过由于实际使用的UCS2，或者UCS4的BMP必然小于0x10000，所以就目前而言，可以认为UTF-16和UCS-2基本相同。但UCS-2只是一个编码方案，UTF-16却要用于实际的传输，所以就不得不考虑字节序的问题。 5、UTF的字节序和BOM 　　UTF-8以字节为编码单元，没有字节序的问题。UTF-16以两个字节为编码单元，在解释一个UTF-16文本前，首先要弄清楚每个编码单元的字节序。例如“奎”的Unicode编码是594E，“乙”的Unicode编码是4E59。如果我们收到UTF-16字节流“594E”，那么这是“奎”还是“乙”？ 　　Unicode规范中推荐的标记字节顺序的方法是BOM。BOM不是“Bill Of Material”的BOM表，而是Byte order Mark。BOM是一个有点小聪明的想法： 　　在UCS编码中有一个叫做"ZERO WIDTH NO-BREAK SPACE"的字符，它的编码是FEFF。而FFFE在UCS中是不存在的字符，所以不应该出现在实际传输中。UCS规范建议我们在传输字节流前，先传输字符"ZERO WIDTH NO-BREAK SPACE"。 　　这样如果接收者收到FEFF，就表明这个字节流是Big-Endian的；如果收到FFFE，就表明这个字节流是Little-Endian的。因此字符"ZERO WIDTH NO-BREAK SPACE"又被称作BOM。 　　UTF-8不需要BOM来表明字节顺序，但可以用BOM来表明编码方式。字符"ZERO WIDTH NO-BREAK SPACE"的UTF-8编码是EF BB BF（读者可以用我们前面介绍的编码方法验证一下）。所以如果接收者收到以EF BB BF开头的字节流，就知道这是UTF-8编码了。 　　Windows就是使用BOM来标记文本文件的编码方式的。 6、进一步的参考资料 　　本文主要参考的资料是 "Short overview of ISO-IEC 10646 and Unicode" 。 　　我还找了两篇看上去不错的资料，不过因为我开始的疑问都找到了答案，所以就没有看： 　　"Understanding Unicode A general introduction to the Unicode Standard" 　　"Character set encoding basics Understanding character set encodings and legacy encodings" 　　我写过UTF-8、UCS-2、GBK相互转换的软件包，包括使用Windows API和不使用Windows API的版本。以后有时间的话，我会整理一下放到我的个人主页上(http://fmddlmyy.home4u.china.com )。 附录1 再说说区位码、GB2312、内码和代码页 　　有的朋友对文章中这句话还有疑问： 　　“GB2312的原文还是区位码，从区位码到内码，需要在高字节和低字节上分别加上A0。” 　　我再详细解释一下： 　　“GB2312的原文”是指国家1980年的一个标准《中华人民共和国国家标准 信息交换用汉字编码字符集 基本集 GB 2312-80》。这个标准用两个数来编码汉字和中文符号。第一个数称为“区”，第二个数称为“位”。所以也称为区位码。1-9区是中文符号，16-55区是一级汉字，56-87区是二级汉字。现在Windows也还有区位输入法，例如输入1601得到“啊”。 　　内码是指操作系统内部的字符编码。早期操作系统的内码是与语言相关的.现在的Windows在内部统一使用Unicode，然后用代码页适应各种语言,“内码”的概念就比较模糊了。微软一般将缺省代码页指定的编码说成是内码，在特殊的场合也会说自己的内码是Unicode，例如在GB18030问题的处理上。 　　所谓代码页(code page)就是针对一种语言文字的字符编码。例如GBK的code page是CP936，BIG5的code page是CP950，GB2312的code page是CP20936。 　　Windows中有缺省代码页的概念，即缺省用什么编码来解释字符。例如Windows的记事本打开了一个文本文件，里面的内容是字节流：BA、BA、D7、D6。Windows应该去怎么解释它呢？ 　　是按照Unicode编码解释、还是按照GBK解释、还是按照BIG5解释，还是按照ISO8859-1去解释？如果按GBK去解释，就会得到“汉字”两个字。按照其它编码解释，可能找不到对应的字符，也可能找到错误的字符。所谓“错误”是指与文本作者的本意不符，这时就产生了乱码。 　　答案是Windows按照当前的缺省代码页去解释文本文件里的字节流。缺省代码页可以通过控制面板的区域选项设置。记事本的另存为中有一项ANSI，其实就是按照缺省代码页的编码方法保存。 　　Windows的内码是Unicode，它在技术上可以同时支持多个代码页。只要文件能说明自己使用什么编码，用户又安装了对应的代码页，Windows就能正确显示，例如在HTML文件中就可以指定charset。 　　有的HTML文件作者，特别是英文作者，认为世界上所有人都使用英文，在文件中不指定charset。如果他使用了0x80-0xff之间的字符，中文Windows又按照缺省的GBK去解释，就会出现乱码。这时只要在这个html文件中加上指定charset的语句，例如： 如果原作者使用的代码页和ISO8859-1兼容，就不会出现乱码了。 　　再说区位码，啊的区位码是1601，写成16进制是0x10,0x01。这和计算机广泛使用的ASCII编码冲突。为了兼容00-7f的ASCII编码，我们在区位码的高、低字节上分别加上A0。这样“啊”的编码就成为B0A1。我们将加过两个A0的编码也称为GB2312编码，虽然GB2312的原文根本没提到这一点。

         1. UTF16

         2. UTF8

         3. UTF32

         4. BMP

            　　UCS-4根据最高位为0的最高字节分成2^7=128个group。每个group再根据次高字节分为256个plane。每个plane根据第3个字节分为256行(rows)，每行包含256个cells。当然同一行的cells只是最后一个字节不同，其余都相同。 　　group 0的plane 0被称作Basic Multilingual Plane, 即BMP。或者说UCS-4中，高两个字节为0的码位被称作BMP。 　　将UCS-4的BMP去掉前面的两个零字节就得到了UCS-2。在UCS-2的两个字节前加上两个零字节，就得到了UCS-4的BMP。而目前的UCS-4规范中还没有任何字符被分配在BMP之外。

      2. MBCS

         [转]常用字符集编码详解 转自：http://www.douban.com/group/topic/6922168/ ASCII ASCII码是7位编码，编码范围是0×00-0×7F。ASCII字符集包括英文字母、阿拉伯数字和标点符号等字符。其中0×00-0×20和 0×7F共33个控制字符。 只支持ASCII码的系统会忽略每个字节的最高位，只认为低7位是有效位。HZ字符编码就是早期为了在只支持7位ASCII系统中传输中文而设计的编码。早期很多邮件系统也只支持ASCII编码，为了传输中文邮件必须使用BASE64或者其他编码方式。 GB2312 GB2312是基于区位码设计的，区位码把编码表分为94个区，每个区对应94个位，每个字符的区号和位号组合起来就是该汉字的区位码。区位码一般用10进制数来表示，如1601就表示16区1位，对应的字符是“啊”。在区位码的区号和位号上分别加上0xA0就得到了 GB2312编码。 区位码中01-09区是符号、数字区，16-87区是汉字区，10-15和88-94是未定义的空白区。它将收录的汉字分成两级：第一级是常用汉字计 3755个，置于16-55区，按汉语拼音字母/笔形顺序排列；第二级汉字是次常用汉字计3008个，置于56-87区，按部首/笔画顺序排列。一级汉字是按照拼音排序的，这个就可以得到某个拼音在一级汉字区位中的范围，很多根据汉字可以得到拼音的程序就是根据这个原理编写的。 GB2312字符集中除常用简体汉字字符外还包括希腊字母、日文平假名及片假名字母、俄语西里尔字母等字符，未收录繁体中文汉字和一些生僻字。可以用繁体汉字测试某些系统是不是只支持GB2312编码。 GB2312的编码范围是0xA1A1-0×7E7E，去掉未定义的区域之后可以理解为实际编码范围是0xA1A1-0xF7FE。 EUC-CN可以理解为GB2312的别名，和GB2312完全相同。 区位码更应该认为是字符集的定义，定义了所收录的字符和字符位置，而GB2312及EUC-CN是实际计算机环境中支持这种字符集的编码。HZ和 ISO- 2022-CN是对应区位码字符集的另外两种编码，都是用7位编码空间来支持汉字。区位码和GB2312编码的关系有点像 Unicode和UTF-8。 GBK GBK编码是GB2312编码的超集，向下完全兼容GB2312，同时GBK收录了Unicode基本多文种平面中的所有CJK汉字。同 GB2312一样，GBK也支持希腊字母、日文假名字母、俄语字母等字符，但不支持韩语中的表音字符（非汉字字符）。GBK还收录了GB2312不包含的汉字部首符号、竖排标点符号等字符。 GBK的整体编码范围是为0×8140-0xFEFE，不包括低字节是0×7F的组合。高字节范围是0×81-0xFE，低字节范围是 0×40-7E和0×80-0xFE。 低字节是0×40-0×7E的GBK字符有一定特殊性，因为这些字符占用了ASCII码的位置，这样会给一些系统带来麻烦。 有些系统中用0×40-0×7E中的字符（如“|”）做特殊符号，在定位这些符号时又没有判断这些符号是不是属于某个 GBK字符的低字节，这样就会造成错误判断。在支持GB2312的环境下就不存在这个问题。需要注意的是支持GBK的环境中小于0×80的某个字节未必就是ASCII符号；另外就是最好选用小于0×40的ASCII符号做一些特殊符号，这样就可以快速定位，且不用担心是某个汉字的另一半。Big5编码中也存在相应问题。 CP936和GBK的有些许差别，绝大多数情况下可以把CP936当作GBK的别名。 GB18030 GB18030编码向下兼容GBK和GB2312，兼容的含义是不仅字符兼容，而且相同字符的编码也相同。GB18030收录了所有 Unicode3.1中的字符，包括中国少数民族字符，GBK不支持的韩文字符等等，也可以说是世界大多民族的文字符号都被收录在内。 GBK和GB2312都是双字节等宽编码，如果算上和ASCII兼容所支持的单字节，也可以理解为是单字节和双字节混合的变长编码。GB18030 编码是变长编码，有单字节、双字节和四字节三种方式。 GB18030的单字节编码范围是0×00-0×7F，完全等同与ASCII；双字节编码的范围和GBK相同，高字节是0×81-0xFE，低字节的编码范围是0×40-0×7E和0×80-FE；四字节编码中第一、三字节的编码范围是0×81-0xFE，二、四字节是0×30-0×39。 Windows中CP936代码页使用0×80来表示欧元符号，而在GB18030编码中没有使用0×80编码位，用其他位置来表示欧元符号。这可以理解为是GB18030向下兼容性上的一点小问题；也可以理解为0×80是CP936对GBK的扩展，而GB18030只是和GBK兼容良好。 unicode 每一种语言的不同的编码页，增加了那些需要支持不同语言的软件的复杂度。因而人们制定了一个世界标准，叫做unicode。unicode为每个字符提供了唯一的特定数值，不论在什么平台上、不论在什么软件中，也不论什么语言。也就是说，它世界上使用的所有字符都列出来，并给每一个字符一个唯一特定数值。 Unicode的最初目标，是用1个16位的编码来为超过65000字符提供映射。但这还不够，它不能覆盖全部历史上的文字，也不能解决传输的问题 (implantation head-ache’s)，尤其在那些基于网络的应用中。已有的软件必须做大量的工作来程序16位的数据。 因此，Unicode用一些基本的保留字符制定了三套编码方式。它们分别是UTF-8,UTF-16和UTF-32。正如名字所示，在 UTF－8中，字符是以8位序列来编码的，用一个或几个字节来表示一个字符。这种方式的最大好处，是UTF－8保留了ASCII字符的编码做为它的一部分，例如，在UTF－8和ASCII中，“A”的编码都是0×41. UTF－16和UTF－32分别是Unicode的16位和32位编码方式。考虑到最初的的目的，通常说的Unicode就是指UTF-16。在讨论 Unicode时，搞清楚哪种编码方式非常重要。 UTF-8 Unicode Transformation Format-8bit，允许含BOM，但通常不含BOM。是用以解决国际上字符的一种多字节编码，它对英文使用8位（即一个字节），中文使用24为（三个字节）来编码。UTF-8包含全世界所有国家需要用到的字符，是国际编码，通用性强。UTF-8编码的文字可以在各国支持UTF8字符集的浏览器上显示。如，如果是UTF8编码，则在外国人的英文IE上也能显示中文，他们无需下载IE的中文语言支持包。 GBK的文字编码是用双字节来表示的，即不论中、英文字符均使用双字节来表示，为了区分中文，将其最高位都设定成1。GBK包含全部中文字符，是国家编码，通用性比UTF8差，不过UTF8占用的数据库比GBD大。 GBK、GB2312等与UTF8之间都必须通过Unicode编码才能相互转换： GBK、GB2312－－Unicode－－UTF8 UTF8－－Unicode－－GBK、GB2312 对于一个网站、论坛来说，如果英文字符较多，则建议使用UTF－8节省空间。不过现在很多论坛的插件一般只支持GBK。

         1. GB-2312

         2. GBK/GB-18030/...

      3. Endian

   4. XML

   5. DB

      1. Concept

         1. ACID

            1. ISO/IEC 10026-1:1992

            2. Atomicity

            3. Consistency

            4. Isolation

            5. Durability

         2. CAP

            1. Consistency

            2. Availability

            3. Tolerance of network Partition

         3. BASE (for No SQL)

            1. Basically Available

            2. Soft-state

            3. Eventual Consistency

      2. Type

         1. RDBMS

         2. Key-Value

         3. Other Obsolete Ones

      3. SQL

         1. Join

            1. Left

            2. Right

            3. Inner

            4. Outer

            5. Cross

   6. Byzantine Generals Problem

      1. Two Generals Problem

   7. 37 Rule (optimal)

   8. 5 Whys

      From Wikipedia, the free encyclopedia The 5 Whys is a question-asking method used to explore the cause/effect relationships underlying a particular problem. Ultimately, the goal of applying the 5 Whys method is to determine a root cause of a defect or problem. Contents * 1 Example * 2 History * 3 Criticism * 4 See also * 5 References Example The following example demonstrates the basic process: * My car will not start. (the problem) 1. Why? - The battery is dead. (first why) 2. Why? - The alternator is not functioning. (second why) 3. Why? - The alternator belt has broken. (third why) 4. Why? - The alternator belt was well beyond its useful service life and has never been replaced. (fourth why) 5. Why? - I have not been maintaining my car according to the recommended service schedule. (fifth why, a root cause) * I will start maintaining my car according to the recommended service schedule. (solution) The questioning for this example could be taken further to a sixth, seventh, or even greater level. This would be legitimate, as the "five" in 5 Whys is not gospel; rather, it is postulated that five iterations of asking why is generally sufficient to get to a root cause. The real key is to encourage the troubleshooter to avoid assumptions and logic traps and instead to trace the chain of causality in direct increments from the effect through any layers of abstraction to a root cause that still has some connection to the original problem. Note that in this example the fifth why suggests a broken process or an alterable behavior, which is typical of reaching the root-cause level. History The technique was originally developed by Sakichi Toyoda and was later used within Toyota Motor Corporation during the evolution of their manufacturing methodologies. It is a critical component of problem solving training delivered as part of the induction into the Toyota Production System. The architect of the Toyota Production System, Taiichi Ohno, described the 5 whys method as "the basis of Toyota's scientific approach . . . by repeating why five times, the nature of the problem as well as its solution becomes clear."[1] The tool has seen widespread use beyond Toyota, and is now used within Kaizen, lean manufacturing, and Six Sigma. Criticism While the 5 Whys is a powerful tool for engineers or technically savvy individuals to help get to the true causes of problems, it has been criticized by Teruyuki Minoura, former managing director of global purchasing for Toyota, as being too basic a tool to analyze root causes to the depth that is needed to ensure that the causes are fixed. Reasons for this criticism include: * Tendency for investigators to stop at symptoms rather than going on to lower level root causes. * Inability to go beyond the investigator's current knowledge - can't find causes that they don't already know * Lack of support to help the investigator to ask the right "why" questions. * Results aren't repeatable - different people using 5 Whys come up with different causes for the same problem. * The tendency to isolate a single root cause, whereas each question could elicit many different root causes These can be significant problems when the method is applied through deduction only. On-the-spot verification of the answer to the current "why" question, before proceeding to the next, is recommended as a good practice to avoid these issues.[2] 公司办公大楼的外墙为什么每年都要定期维修？ • 墙壁每天需要清洗，导致墙壁受到酸蚀损害——为什么？ • 大楼每天被大量的鸟粪弄脏——为什么？ • 大楼周围经常聚集很多燕子——为什么？ • 大楼上有许多燕子爱吃的蜘蛛——为什么？ • 墙上有蜘蛛最爱吃的飞虫——为什么？ • 这里的尘埃最适于飞虫繁殖——为什么？ • 尘埃和从窗子照射进来的光线刺激了飞虫的繁殖欲 解决方案：拉上窗帘

   9. OS

      1. Process

         1. The Process VM

            1. Register

            2. Memory

            3. IO Device

         2. Thread

            1. On Linux

               1. LinuxThreads

               2. NPTL

         3. Process Scheduler

            1. MRU

            2. ...

      2. Resource

      3. Time Constraint

         1. Realtime OS

            1. Hard Realtime

            2. Soft Realtime

         2. Time Sharing OS

      4. System Call

      5. Lock

         1. Mutex

         2. Semaphore (P-V)

         3. Atom

         4. SpinLock

         5. RW-Lock

         6. Seq Lock

            1. Updating Jiffies

         7. RCU(Read Copy Update) Lock

         8. Critical Section (Windows)

   10. Software Engineering

       1. Agile

          1. TDD

             1. The 3 Laws of TDD

                http://butunclebob.com/ArticleS.UncleBob.TheThreeRulesOfTdd The Three Laws of TDD. Over the years I have come to describe Test Driven Development in terms of three simple rules. They are: 1. You are not allowed to write any production code unless it is to make a failing unit test pass. 2. You are not allowed to write any more of a unit test than is sufficient to fail; and compilation failures are failures. 3. You are not allowed to write any more production code than is sufficient to pass the one failing unit test. You must begin by writing a unit test for the functionality that you intend to write. But by rule 2, you can't write very much of that unit test. As soon as the unit test code fails to compile, or fails an assertion, you must stop and write production code. But by rule 3 you can only write the production code that makes the test compile or pass, and no more. If you think about this you will realize that you simply cannot write very much code at all without compiling and executing something. Indeed, this is really the point. In everything we do, whether writing tests, writing production code, or refactoring, we keep the system executing at all times. The time between running tests is on the order of seconds, or minutes. Even 10 minutes is too long. Too see this in operation, take a look at The Bowling Game Kata. Now most programmers, when they first hear about this technique, think: "This is stupid!" "It's going to slow me down, it's a waste of time and effort, It will keep me from thinking, it will keep me from designing, it will just break my flow." However, think about what would happen if you walked in a room full of people working this way. Pick any random person at any random time. A minute ago, all their code worked. Let me repeat that: A minute ago all their code worked! And it doesn't matter who you pick, and it doesn't matter when you pick. A minute ago all their code worked! If all your code works every minute, how often will you use a debugger? Answer, not very often. It's easier to simply hit ^Z a bunch of times to get the code back to a working state, and then try to write the last minutes worth again. And if you aren't debugging very much, how much time will you be saving? How much time do you spend debugging now? How much time do you spend fixing bugs once you've debugged them? What if you could decrease that time by a significant fraction? But the benefit goes far beyond that. If you work this way, then every hour you are producing several tests. Every day dozens of tests. Every month hundreds of tests. Over the course of a year you will write thousands of tests. You can keep all these tests and run them any time you like! When would you run them? All the time! Any time you made any kind of change at all! Why don't we clean up code that we know is messy? We're afraid we'll break it. But if we have the tests, we can be reasonably sure that the code is not broken, or that we'll detect the breakage immediately. If we have the tests we become fearless about making changes. If we see messy code, or an unclean structure, we can clean it without fear. Because of the tests, the code becomes malleable again. Because of the tests, software becomes soft again. But the benefits go beyond that. If you want to know how to call a certain API, there is a test that does it. If you want to know how to create a certain object, there is a test that does it. Anything you want to know about the existing system, there is a test that demonstrates it. The tests are like little design documents, little coding examples, that describe how the system works and how to use it. Have you ever integrated a third party library into your project? You got a big manual full of nice documentation. At the end there was a thin appendix of examples. Which of the two did you read? The examples of course! That's what the unit tests are! They are the most useful part of the documentation. They are the living examples of how to use the code. They are design documents that are hideously detailed, utterly unambiguous, so formal that they execute, and they cannot get out of sync with the production code. But the benefits go beyond that. If you have ever tried to add unit tests to a system that was already working, you probably found that it wasn't much fun. You likely found that you either had to change portions of the design of the system, or cheat on the tests; because the system you were trying to write tests for was not designed to be testable. For example, you'd like to test some function 'f'. However, 'f' calls another function that deletes a record from the database. In your test, you don't want the record deleted, but you don't have any way to stop it. The system wasn't designed to be tested. When you follow the three rules of TDD, all your code will be testable by definition! And another word for "testable" is "decoupled". In order to test a module in isolation, you must decouple it. So TDD forces you to decouple modules. Indeed, if you follow the three rules, you will find yourself doing much more decoupling than you may be used to. This forces you to create better, less coupled, designs. Given all these benfits, these stupid little rules of TDD might not actually be so stupid. They might actually be something fundemental, something profound. Indeed, I had been a programmer for nearly thirty years before I was introduced to TDD. I did not think anyone could teach me a low level programming practice that would make a difference. Thirty years is a lot of experience after all. But when I started to use TDD, I was dumbfounded at the effectiveness of the technique. I was also hooked. I can no longer concieve of typing in a big long batch of code hoping it works. I can no longer tolerate ripping a set of modules apart, hoping to reassemble them and get them all working by next Friday. Every decision I make while programming is driven by the basic need to be executing again a minute from now.

          2. Refactoring

          3. XP

             1. Pair Programming

       2. Traditional Software Engineering

          1. The Waterfall Model

             1. V model of testing

          2. Prototype

       3. SEMAT

          http://www.infoq.com/cn/news/2010/05/semat http://csbabel.wordpress.com/2010/04/07/semat-translation/ http://www.semat.org/bin/view SEMAT於2009成立并发表宣言，不过跟敏捷宣言很不一样： 软件工程目前受到不成熟的实践严重阻碍，具体问题包括： 像时装业流行的时尚多于工程学科 缺乏可靠和普遍接受的理论基础 大量方法及其变种，而其分别缺乏理解或虚假地作大 没有可靠实验评估和验证 业界实践和学术业界存在分歧 我们支持一个根据牢固理论、已证实的原则、最佳实践来重新建立软件工程学： 包括广泛认同和可扩展的核心元素 能处理技术和人为问题 受到业界、学界、研究者和用户所支持 面对需求和技术转变时支持扩展 签名人士包括在软件业界和敏捷社区的人士：Scott Ambler、Barry Boehm、Larry Constantine、Erich Gamma、Tom Gilb、Ellen Gottesdiener、Sam Guckenheimer、Watts Humphrey、Capers Jones、Ivar Jacobson、Philippe Kruchten、Robert Martin、Stephen Mellor、Bertrand Meyer、James Odell、Ken Schwaber、Edward Yourdon... SEMAT的愿景描述联署人士同意去创造的核心内容：“集中去寻找和描述所有软件工程工序中必需的元素，通常例子包括团队合作、项目管理和过程改进．这核心亦会结合一些其他工程学科的概念，这核心必需适应改变。” 目前分成五个工作类别： 定义：定义软件工程同相关概念 理论：寻找相关支持理论（倾向于数学理论） 共同元素：寻找软件工程中的共同元素 核合语言：找到一套语言来描述其他元素 评估：评估软件工程实践和理论的方法 《设计模式》的作者 Ralph Johnson担心学术所谓的“理论”是纯粹数学，而不是业界人士所指的，他还指出连什么是软件工程都不清晰：“是指所有软件开发，还是持有软件工程学位的人所实践的软件开发活动？还是工作头衔上包含软件工程的呢？那些一般银行或者保险公司里的软件开发部门，他们的经理只有少许软件开发背景，而他们一般开发人员可能都没有计算机科学学位，没怎么接受过软件工程正规训练的又如何呢？”他认为软件业界真正的问题在于：很多人没有理会过一些在已经存在三十多年的实践。 Jorge Aranda同意软件业界里存在很多“流行事物”，但指出这些曾经被指为“流行事物”，例如面向对象开发、极限编程等等现在都被主流开发所接受，他担心如果持保守态度下将来的创意会有所局限。 一年前， Tom DeMarco认为软件工程这概念已死，DeMacro怀疑早年关于度量（Metrics）的研究是否仍然有效： “控制软件项目：管理、量度、估计在过去软件工程师量代规划项目时起到重要作用。在自我回顾的时候，我在想，到底这些建议是否在当时正确，现在是否还有用，我是否仍然认为这些度量是成功软件开发中必要的工作？我的管案是：不是，不是，以及不是” 他继续指出：“稳定性和可预测性仍然重要，但已经不是最重要的事情”。 Geert Bellekens支持SEMAT，他指出： 我认为可以稳妥地说我们见识过很多不同方法学，但他们背后都很类似。 如果我们把这些方法学放在一起，从远距离观看，我们都可以看出他们相似和不同的地方。 而这正是SEMAT所做的事情，尝试找出他们共同之处，以一套中立的方式表达出来。 Scott Ambler 亦支持SEMAT，认为业界需要比现在更好的方法，能够有很多人参与，他也希望SEMAT可以产出有价值的东西。 Alistair Cockburn曾参与SEMAT会议，但现在选择退出，他在文中有五点重点： 他们提出行动的请求基于未仔细研究甚至逻辑不通的论据；他以新一套“流行用语”来代替旧的“流行用语”，他内里自相矛盾，提出的问题没得到解决，而提出的解决方案根本不对题，提出的路线没有公正性，根本是误导，透过权力、夸张宣传和野心来产生支持。 组织者不关心我所关心的题目。 他们没什么机会会提到工程或者工程理论，更适合他们的名字是 "超过程核心"（“Meta-Process-Kernel”） 行动。 他们造出来的东西很难会对业界有什么影响。 他们在短期内做到什么的概率很低。 Martin Fowler亦有被邀请参与SEMAT，持有类似观点： 人才是软件开发中最中心的元素，而人却是不能预测的，尝试去找出共同过程元素只会是白费工夫，除非有一天，人变成可以用数学描述的。 您对SEMAT有什么想法呢？会局限将来创意吗？它会创造任何有价值的事情？还是真正的问题在于团队根本不知道自己忽略了重要的软件工程实践？欢迎您在文后留下您的观点。

       4. Methods

          1. Code Review

          2. Unit Test

          3. Pair Programming (XP)

   11. Parallel

       1. Locking

          1. SMP

          2. Thread

          3. Shared Data

       2. Non-locking

          1. Process

             1. OS Process (VM)

             2. IPC

             3. Lightweight Process e.g. Erlang

          2. Message

          3. Transactions: CAS, STM

       3. Concept

          1. Parallel vs Concurrency

   12. Security

       1. Cryptography

          1. Symmetric-key Algorithm

             1. DES

             2. 3DES

             3. IDEA

          2. Public-key Algorithm

             1. RSA

          3. Message Digest

             1. MD5

             2. SHA-1

          4. Attack

             1. Brute Force

             2. MITM (Man-in-the-middle)

       2. Common Weakness

          1. SQL Injection

          2. Buffer Overflow

          3. Heap Spraying

             1. Network Attack & VM

   13. Chromatology

   14. Book

       1. Language

          1. C++

             1. STL

          2. LISP

          3. Erlang

          4. Python

       2. OS

       3. TAOUP

       4. Software Engineering

          1. The Mythical Man-Month

          2. Peopleware

          3. The Deadline: A Novel About Project Management

          4. Waltzing with Bears: Managing Risk on Software Projects

          5. XP Explained

          6. TDD - ...

          7. Getting Real by 37 Signals

       5. Virtual Machine

       6. Hardware

       7. Compiler

   15. Viewpoints

       1. Worse Is Better

          1. New Jersey vs MIT

             http://www.jwz.org/doc/worse-is-better.html The Rise of ``Worse is Better'' By Richard Gabriel I and just about every designer of Common Lisp and CLOS has had extreme exposure to the MIT/Stanford style of design. The essence of this style can be captured by the phrase ``the right thing.'' To such a designer it is important to get all of the following characteristics right: * Simplicity-the design must be simple, both in implementation and interface. It is more important for the interface to be simple than the implementation. * Correctness-the design must be correct in all observable aspects. Incorrectness is simply not allowed. * Consistency-the design must not be inconsistent. A design is allowed to be slightly less simple and less complete to avoid inconsistency. Consistency is as important as correctness. * Completeness-the design must cover as many important situations as is practical. All reasonably expected cases must be covered. Simplicity is not allowed to overly reduce completeness. I believe most people would agree that these are good characteristics. I will call the use of this philosophy of design the ``MIT approach.'' Common Lisp (with CLOS) and Scheme represent the MIT approach to design and implementation. The worse-is-better philosophy is only slightly different: * Simplicity-the design must be simple, both in implementation and interface. It is more important for the implementation to be simple than the interface. Simplicity is the most important consideration in a design. * Correctness-the design must be correct in all observable aspects. It is slightly better to be simple than correct. * Consistency-the design must not be overly inconsistent. Consistency can be sacrificed for simplicity in some cases, but it is better to drop those parts of the design that deal with less common circumstances than to introduce either implementational complexity or inconsistency. * Completeness-the design must cover as many important situations as is practical. All reasonably expected cases should be covered. Completeness can be sacrificed in favor of any other quality. In fact, completeness must sacrificed whenever implementation simplicity is jeopardized. Consistency can be sacrificed to achieve completeness if simplicity is retained; especially worthless is consistency of interface. Early Unix and C are examples of the use of this school of design, and I will call the use of this design strategy the ``New Jersey approach.'' I have intentionally caricatured the worse-is-better philosophy to convince you that it is obviously a bad philosophy and that the New Jersey approach is a bad approach. However, I believe that worse-is-better, even in its strawman form, has better survival characteristics than the-right-thing, and that the New Jersey approach when used for software is a better approach than the MIT approach. Let me start out by retelling a story that shows that the MIT/New-Jersey distinction is valid and that proponents of each philosophy actually believe their philosophy is better. Two famous people, one from MIT and another from Berkeley (but working on Unix) once met to discuss operating system issues. The person from MIT was knowledgeable about ITS (the MIT AI Lab operating system) and had been reading the Unix sources. He was interested in how Unix solved the PC loser-ing problem. The PC loser-ing problem occurs when a user program invokes a system routine to perform a lengthy operation that might have significant state, such as IO buffers. If an interrupt occurs during the operation, the state of the user program must be saved. Because the invocation of the system routine is usually a single instruction, the PC of the user program does not adequately capture the state of the process. The system routine must either back out or press forward. The right thing is to back out and restore the user program PC to the instruction that invoked the system routine so that resumption of the user program after the interrupt, for example, re-enters the system routine. It is called ``PC loser-ing'' because the PC is being coerced into ``loser mode,'' where ``loser'' is the affectionate name for ``user'' at MIT. The MIT guy did not see any code that handled this case and asked the New Jersey guy how the problem was handled. The New Jersey guy said that the Unix folks were aware of the problem, but the solution was for the system routine to always finish, but sometimes an error code would be returned that signaled that the system routine had failed to complete its action. A correct user program, then, had to check the error code to determine whether to simply try the system routine again. The MIT guy did not like this solution because it was not the right thing. The New Jersey guy said that the Unix solution was right because the design philosophy of Unix was simplicity and that the right thing was too complex. Besides, programmers could easily insert this extra test and loop. The MIT guy pointed out that the implementation was simple but the interface to the functionality was complex. The New Jersey guy said that the right tradeoff has been selected in Unix-namely, implementation simplicity was more important than interface simplicity. The MIT guy then muttered that sometimes it takes a tough man to make a tender chicken, but the New Jersey guy didn't understand (I'm not sure I do either). Now I want to argue that worse-is-better is better. C is a programming language designed for writing Unix, and it was designed using the New Jersey approach. C is therefore a language for which it is easy to write a decent compiler, and it requires the programmer to write text that is easy for the compiler to interpret. Some have called C a fancy assembly language. Both early Unix and C compilers had simple structures, are easy to port, require few machine resources to run, and provide about 50%--80% of what you want from an operating system and programming language. Half the computers that exist at any point are worse than median (smaller or slower). Unix and C work fine on them. The worse-is-better philosophy means that implementation simplicity has highest priority, which means Unix and C are easy to port on such machines. Therefore, one expects that if the 50% functionality Unix and C support is satisfactory, they will start to appear everywhere. And they have, haven't they? Unix and C are the ultimate computer viruses. A further benefit of the worse-is-better philosophy is that the programmer is conditioned to sacrifice some safety, convenience, and hassle to get good performance and modest resource use. Programs written using the New Jersey approach will work well both in small machines and large ones, and the code will be portable because it is written on top of a virus. It is important to remember that the initial virus has to be basically good. If so, the viral spread is assured as long as it is portable. Once the virus has spread, there will be pressure to improve it, possibly by increasing its functionality closer to 90%, but users have already been conditioned to accept worse than the right thing. Therefore, the worse-is-better software first will gain acceptance, second will condition its users to expect less, and third will be improved to a point that is almost the right thing. In concrete terms, even though Lisp compilers in 1987 were about as good as C compilers, there are many more compiler experts who want to make C compilers better than want to make Lisp compilers better. The good news is that in 1995 we will have a good operating system and programming language; the bad news is that they will be Unix and C++. There is a final benefit to worse-is-better. Because a New Jersey language and system are not really powerful enough to build complex monolithic software, large systems must be designed to reuse components. Therefore, a tradition of integration springs up. How does the right thing stack up? There are two basic scenarios: the ``big complex system scenario'' and the ``diamond-like jewel'' scenario. The ``big complex system'' scenario goes like this: First, the right thing needs to be designed. Then its implementation needs to be designed. Finally it is implemented. Because it is the right thing, it has nearly 100% of desired functionality, and implementation simplicity was never a concern so it takes a long time to implement. It is large and complex. It requires complex tools to use properly. The last 20% takes 80% of the effort, and so the right thing takes a long time to get out, and it only runs satisfactorily on the most sophisticated hardware. The ``diamond-like jewel'' scenario goes like this: The right thing takes forever to design, but it is quite small at every point along the way. To implement it to run fast is either impossible or beyond the capabilities of most implementors. The two scenarios correspond to Common Lisp and Scheme. The first scenario is also the scenario for classic artificial intelligence software. The right thing is frequently a monolithic piece of software, but for no reason other than that the right thing is often designed monolithically. That is, this characteristic is a happenstance. The lesson to be learned from this is that it is often undesirable to go for the right thing first. It is better to get half of the right thing available so that it spreads like a virus. Once people are hooked on it, take the time to improve it to 90% of the right thing. A wrong lesson is to take the parable literally and to conclude that C is the right vehicle for AI software. The 50% solution has to be basically right, and in this case it isn't. But, one can conclude only that the Lisp community needs to seriously rethink its position on Lisp design. I will say more about this later. rpg@lucid.com

       2. The Cathedral and the Bazaar

       3. DRY

       4. KISS

       5. TAOUP: Unix Philosophy

          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 simlicity; 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.

       6. Leak of Abstraction

          1. by Joel Spolsky

       7. Law of Demeter (Principle of Least Knowledge)

          http://en.wikipedia.org/wiki/Law_of_Demeter The Law of Demeter (LoD) or Principle of Least Knowledge is a design guideline for developing software, particularly object-oriented programs. In its general form, the LoD is a specific case of loose coupling. The guideline was invented at Northeastern University towards the end of 1987, and can be succinctly summarized in one of the following ways: Each unit should have only limited knowledge about other units: only units "closely" related to the current unit. Each unit should only talk to its friends; don't talk to strangers. Only talk to your immediate friends. The fundamental notion is that a given object should assume as little as possible about the structure or properties of anything else (including its subcomponents). It is so named for its origin in the Demeter Project, an adaptive programming and aspect-oriented programming effort. The project was named in honor of Demeter, “distribution-mother” and the Greek goddess of agriculture, to signify a bottom-up philosophy of programming which is also embodied in the law itself. Contents [hide] 1 In object-oriented programming 2 Advantages and disadvantages 3 See also 4 References 5 Further reading 6 External links [edit]In object-oriented programming When applied to object-oriented programs, the Law of Demeter can be more precisely called the “Law of Demeter for Functions/Methods” (LoD-F). In this case, an object A can request a service (call a method) of an object instance B, but object A cannot “reach through” object B to access yet another object, C, to request its services. Doing so would mean that object A implicitly requires greater knowledge of object B’s internal structure. Instead, B’s class should be modified if necessary so that object A can simply make the request directly of object B, and then let object B propagate the request to any relevant subcomponents. Or A should have a direct reference to object C and make the call directly. If the law is followed, only object B knows its own internal structure. More formally, the Law of Demeter for functions requires that a method M of an object O may only invoke the methods of the following kinds of objects: O itself M's parameters any objects created/instantiated within M O's direct component objects a global variable, accessible by O, in the scope of M In particular, an object should avoid invoking methods of a member object returned by another method. For many modern object oriented languages that use a dot as field identifier, the law can be stated simply as "use only one dot". That is, the code "a.b.Method()" breaks the law where "a.Method()" does not. There is disagreement as to the sufficiency of this approach.[1][2] As a simple example, when one wants to walk a dog, it would be folly to command the dog’s legs to walk directly; instead one commands the dog and lets it take care of its legs itself. [3] [edit]Advantages and disadvantages The advantage of following the Law of Demeter is that the resulting software tends to be more maintainable and adaptable. Since objects are less dependent on the internal structure of other objects, object containers can be changed without reworking their callers. A disadvantage of the Law of Demeter is that it sometimes requires writing a large number of small "wrapper" methods to propagate method calls to the components. Furthermore, a class's interface can become bulky as it hosts methods for contained classes, resulting in a class without a cohesive interface. But this might also be a sign of bad OO design. Basili et al. published experimental results in 1996 suggesting that the Law of Demeter was a valid way to reduce the probability of software faults. A Multilayered architecture can be considered to be a systematic mechanism for implementing the Law of Demeter in a software system. In a layered architecture, code within each layer can only make calls to code within the layer and code within the next layer down. "Layer skipping" would violate the layered architecture. [edit]See also Principle of least astonishment

       8. Principle of Least Astonishment

          http://en.wikipedia.org/wiki/Principle_of_least_astonishment The Principle of Least Astonishment (POLA/PLA) applies to user interface design, software design, and ergonomics. (It is also known as the rule or law of least astonishment, or the principle, rule, or law of least surprise.) The POLA states that, when two elements of an interface conflict, or are ambiguous, the behaviour should be that which will least surprise the user; in particular a programmer should try to think of the behavior that will least surprise someone who uses the program, rather than that behavior that is natural from knowing the inner workings of the program.[1] This practice also involves the application of sensible defaults. Contents [hide] 1 Examples 2 See also 3 References 4 External links [edit]Examples A user interface may have the behaviour that pressing Ctrl+Q causes the program to quit. The same user interface may have a facility for recording macros, a sequence of keystrokes to be played back later, intended to be able to control all aspects of the program. The user may want to record a keystroke sequence that includes Ctrl+Q as part (most likely the last part) of the macro. The principle says that pressing Ctrl+Q while recording a macro should not quit the program (which would surprise the user), but rather should record the keystroke. [edit]See also DWIM Occam's razor Law of Demeter (also known as the "principle of least knowledge")

       9. Do What I Mean (DWIM)

          http://en.wikipedia.org/wiki/DWIM The acronym DWIM stands for "Do What I Mean". It is a humorous way of describing a user's feeling that a computer function should work the way the user wants — instead of the actual result that they told it to do, but did not want. The term has been in use for decades.[1] Anticipating variations in the way a user or a programmer expresses themselves has a long history. Before 1984, Warren Teitelman wrote routines to "correct errors automatically or with minor user intervention".[2] Following in the LISP tradition, Emacs has a function comment-dwim that comments out a selected region if uncommented, or uncomments it, when already commented out.

   16. HCI

       1. Scientific Laws

          1. Fitt's Law

             1. Steering Law

          2. Hick's Law

          3. The Power Law of Practice

          4. Law of Cross

       2. Other Laws

          1. 3 Clicks

          2. 2 Seconds

          3. 400 ms

          4. Don't Make Me Think

          5. Breadcrumbs & Threads

       3. Cognitive Science

          1. Cognitive Psychology

       4. HCI vs HMI vs GUI

       5. Type

          1. WIMP

          2. ZUI

          3. Attentive UI

          4. Touch

             1. Type by NumPoints

                1. Single Touch

                2. MultiTouch

             2. Type by Principle

          5. Gesture

       6. Examples

          1. Pie Menus

          2. Snap

          3. SplitView (Mercedes & Bosch)

   17. Psychology

       1. To Be Updated

   18. Accessibility

       1. Section 508

       2. WCAG

   19. Computer Vision

       1. 3D Reconstruction

          1. 3D Camera

          2. Stereo/Disparity

       2. AR (Augmented Reality)

       3. To Be Updated

   20. Design

       1. Font

          1. Terms

             1. Baseline

             2. Capline

             3. X-Height

             4. Serif

             5. Ascender/Descender Line, Capline

             6. Check this out

                http://csbabel.wordpress.com/2010/01/05/baseline-is-only-the-beginning/ 《只知道baseline是远远不够的——字体资料》

          2. Serif vs Sans Serif

          3. Headline vs Content

          4. Arial vs Helvetica

          5. Outline(TrueType) vs Bitmap

       2. To Be Updated