Mark's bookcase: programming

Fitzpatrick 提到他為LiveJournal/Google招聘程式設計師時提到

"我總是找這種型別的人，他們會做很多別人沒要求他做的事，不僅是學校的專案或者前僱主要求他做的，他們對某些事情充滿熱情，有額外的專案。”

”HR的經驗中有這麼一條--- 一些人只會做讓他們做的事，沒有那種追求極致的熱情。他們會說：做好了，接下來幹什麼？他們甚至不告訴你，自己就上網玩去了。“

他們在面試你時問了什麼? “任意長度的十進位數字字串相乘”
many solutions!

#!/usr/bin/env python
 
def digits(x):
    return [int(c) for c in str(x)]
 
def mult_table(xs, ys):
    return [[x * y for x in xs] for y in ys]
 
def polymul(xs, ys):
    return map(lambda *vs: sum(filter(None, vs)),
               *[[0] * i + zs for i, zs in enumerate(mult_table(xs, ys))])
 
def longmult(x, y):
    result = 0
    for v in polymul(digits(x), digits(y)):
        result = result * 10 + v
    return result
 
if __name__ == "__main__":
    print longmult(2**64, 2**64)

“Callgrind"
Profile你的程式，哪些function用去了最多的instruction

670,486  src/lcthw/bstrlib.c:bstrcmp [tests/bstree_tests]
  194,377  src/lcthw/bstree.c:BSTree_get [tests/bstree_tests]
   65,580  src/lcthw/bstree.c:default_compare [tests/bstree_tests]
   16,338  src/lcthw/bstree.c:BSTree_delete [tests/bstree_tests]
   13,000  src/lcthw/bstrlib.c:bformat [tests/bstree_tests]
   11,000  src/lcthw/bstrlib.c:bfromcstralloc [tests/bstree_tests]
    7,774  src/lcthw/bstree.c:BSTree_set [tests/bstree_tests]
    5,800  src/lcthw/bstrlib.c:bdestroy [tests/bstree_tests]
    2,323  src/lcthw/bstree.c:BSTreeNode_create [tests/bstree_tests]
    1,183  /private/tmp/pkg-build/coregrind//vg_preloaded.c:vg_cleanup_env [/usr/local/lib/valgrind/vgpreload_core-amd64-darwin.so]

，甚至清楚地指出哪一行的程式碼呢！

2,453  static inline BSTreeNode *BSTree_getnode(BSTree *map, BSTreeNode *node, void *key)
     .  {
61,853      int cmp = map->compare(node->key, key);
663,908  => src/lcthw/bstree.c:default_compare (14850x)
     .
14,850      if(cmp == 0) {
     .          return node;
24,794      } else if(cmp < 0) {
30,623          if(node->left) {
     .              return BSTree_getnode(map, node->left, key);
     .          } else {
     .              return NULL;
     .          }
     .      } else {
13,146          if(node->right) {
     .              return BSTree_getnode(map, node->right, key);
     .          } else {
     .              return NULL;
     .          }
     .      }
     .  }
”我覺得有些人只是在工作，而不是享受城市設計帶來的樂趣，這沒什麼問題。但把他們和那些核心程式師做比較就不行了，當一個人花的時間多十倍，不停地考慮怎麼寫好這程式，另一個人只為了工作而工作，那兩者的生產力上的差距又豈止十倍呢?“

你是因為覺得有趣才設計程式的? “是的，我還是會繼續做些小玩意，我的手機上有個無聊的棋類遊戲，我對她有點厭煩了，所以就寫了一個求解程式，其中試用了一些動態程式設計，處理不同的棋盤大小，還有很多隨機棋盤，解決棋局所需步數的長條圖。我把它發給作者..這是剪很有意思的事情，我想我可以退休後整天做這些事。”

src: 
http://c.learncodethehardway.org/book/ex41.html
http://rosettacode.org/wiki/Long_multiplication#Python

Enable all optional compiler warnings.
Lint.
Maintain both ship and debug versions of your program.
Use assertions to validate function arguments.


#ifdef DEBUG
    void _Assert(char*, unsigned); /*prototype*/
    #define ASSERT(f)\
      if(f)          \
        {}           \
      else           \
        _Assert(__FILE__, __LINE__)

#else
    #define ASSERT(f)
#endif

void _Assert(char *strFile, unsigned uLine)
{
  fflush(NULL);
  fprintf(stderr, "\nAssertion failed: %s, line %u\n", 
           strFile, uLine);
  fflush(stderr);
  abort();
}

Strip undefined behavior from your code, or user assertions to catch illegal users of undefined behavior.

Don't waste people's time. Document unclear assertions.

/* Blocks overlap? Use memmove. */
ASSERT(pbTo>=pbFrom+size || pbFrom >= pbTo+size);

Either remove implicit assumptions, or assert that they are valid.
Use Assertions to detect impossible conditions.
Don't hide bugs when you program defensively.
Use a second algorithm to validate your results.

implement an ASSERT macro that the file name string(__FILE__) would be defined just once per file:
bury the details in a new ASSERTFILE macro that you use once at the start of each source file


  #ifdef DEBUG
    #define ASSERTFILE(str)    \
              static char strAssertFile[] = str;

    #define ASSERT(f)          \
              if(f)            \
                {}             \
              else             \
                _Assert(strAssertFile, __LINE__)
  #else
    #define ASSERTFILE(str)
    #define ASSERT(f)
  #endif

Eliminate random behavior. Force bugs to be reproducible.

#define bGarbage 0xA3
flag fNewMemory(void **ppv, size_t size)
{
  byte **ppb=(byte**)ppv;
  ASSERT(ppv!=NULL && size!=0);
  *ppb=(byte*)malloc(size);
  #ifdef DEBUG
  {
     if(*ppb != NULL)
       memset(*ppb, bGarbage, size);
  }
  #endif
  return (*ppb != NULL);
}

Destroy your garbage so that it's not misused.
If something happens rarely, force it to happen often.

Once you release memory, you don't own it, so you shouldn't touch it.
(some memory managers use free memory to store free-chain information, or other internal implementation data) Programmers either don't know, or regularly forget, that realloc can move blocks. Detecting this problem is important. =>
Stimulate what realloc does:
If the block is shrinking, pre-fill the soon-to-be released memory. If the block is expanding, force it to move(instead of expanding in place) by faking a realloc. If the block is the same size, don't to anything.

Remember that debug code is extra code, not different code. Unless there is a compelling reason not to, you should always execute the ship code, even if it's redundant.

Keep debug information to allow stronger error checking.
Design your test carefully, nothing should be arbitrary.

Choosing a value for bGarbage, recursed over the symbol table's tree structure with a pre-order traversal. Some choices are better than others.

Setting "undefined" memory to a constant garbage value is one example of removing random behavior.
Make sure your tests work even for programmers who are unaware of them. The best tests are those that require no knowledge of their existence.

Programmers occasionally write coe that fills past the end of an allocated memory block. How you could enhance the memory subsystem checks to alert you to these types of bugs.

Allocate 1 extra byte for every block that you allocate: 檢查DebugByte有沒有被覆寫過去


#define dDebugByte 0xE1

#ifdef DEBUG
  #define sizeofDebugByte 1
#else
  #define sizeofDebugByte 0
#endif


flag fNewMemory(void **ppv, size_t size)
{
  byte **ppb = (byte**)ppv;
  ASSERT(ppv!=NULL && size !=0);
  *ppb = (byte*) malloc(size+sizeofDebugByte);

  #ifdef DEBUG
  {
    if(*ppb!=NULL)
    {
      *(*ppb+size)=dDebugByte;
      memset(*ppb, bGarbage, size);
      .
      .
      .


flag fResizeMemory(void **ppv, size_t sizeNew)
{
  byte **ppb = (**byte) ppv;
  byte *pbNew;
  .
  .
  .
  pbNew = (byte*)realloc(*ppb, sizeNew+sizeofDebugByte);
  if(pbNew!=NULL)
  {
    #ifdef DEBUG
    {
      *(pbNew+sizeNew)=dDebugByte;
      .
      .
      .


/* Verify that nothing wrote off end of block. */
ASSERT(*(pbi->pb + pbi->size) == dDebugByte);

how could you give testers the ability to fake out-of-memory conditions?
Normally by using a tool to gobble memory until the application's memory requests begin to fails.
It works, but not very precise --- it cause some allocation request somewhere in the program fail.
A better technique is to build an out-of-memory simulator directly into the memory manager.

在newMemory時，或在resizeMemory時，add an if statement


#ifdef DEBUG
  if(fFakeFailure(&fiMemory))
  {
    *ppb=NULL;
    return (FALSE);
  }
#endif

With these changes, the failure mechanism is in place. To make it work, you would call the SetFailure routine to initialize the failureinfo struct:


/* tell the failure system that you want to call the system five times before getting seven consecutive failures. */
SetFailures(&fiMemory, 5, 7); 

/* tow common calls to SetFailures: Don't fake any failures. Always fake failures */
SetFailures(&fiMemory, UNIT_MAX, 0);
SetFailures(&fiMemory, 0, UNIT_MAX);

The code below implements the four functions that make up the failure mechanism.


typedef struct
{
  unsigned nSucceed; /* # of calls before failing */
  unsigned nFail;    /* # of times to fail        */
  unsigned nTries;   /* # of times already called */
  int lock;          /* if > 0, disable mechanism.*/
} failureinfo;

void SetFailures(failureinfo *pfi, unsigned nSucceed, 
                  unsigned nFail)
{
  /* If nFail is 0, require that nSucceed be UNIT_MAX. */
  ASSERT(nFail != 0 || nSucceed == UINT_MAX);

  pfi->nSucceed = nSucceed;
  pfi->nFail    = nFail;
  pfi->nTries   = 0;
  pfi->lock     = 0;
}

void EnableFailures(failuresinfo *pfi)
{
  ASSERT(pfi->lock > 0);
  pfi->lock--;
}

void DisableFailures(failuresinfo *pfi)
{
  ASSERT(pfi->lock >=0 && pfi->lock < INT_MAX);
  pfi->lock++;
}

flag fFakeFailure(failureinfo *pfi)
{
  ASSERT(pfi != NULL);
  if(pfi->lock > 0)
    return (FALSE);

  /* Pin nTries at UINT_MAX. */
  if(pfi->nTries != UINT_MAX)
    pfi->nTries++;

  if(pfi->nTries <= pfi->nSucceed)
    return (FALSE);

  if(pfi->nTries - pfi->nSucceed <= pfi->nFail)
    return (TURE);

  return (FALSE);
}

Don't wait until you have a bug to step through your code
Step through every path (more than one code path: if and switch statements, &&, || and ?: operators)
As you step through code, focus on data flow ( Overflow and underflow bugs, Data conversion bugs, Off-by-one bugs, NULL pointer bugs, Bugs using garbage memory(oxA3 bugs), Assignment bugs in which you've use = instead of ==, Precedence bugs, Logic bugs, )
Source leve debuggers can hide execution details. Step through critical code at the instruction level.
Bugs don't grow in code spontaneously; they are the result of a programmer's writing new code or changing existing code. If you want to find bugs in your code, there is no better method than stepping through eery line of the code the moment it's compiled.
The problem with black-box testing is that you can't tell what goes on between stuffing in the inputs and receiving the outputs. The best way to catch bugs is to look for them the moment you write or change code. I don't know how many programmers who consistently write bug-free code, but the few I do know habitually step through all of their code

Make it hard to ignore error conditions. Don't bury error code in return values.
Always look for, and eliminate, flaws in your interfaces.
Don't write multipurpose functions. Write separate functions to allow stronger argument validation.
Don't be wishy-washy. Define explicit function arguments.

getchar returns int

realloc return null (Ideally, realloc would always return an error code and a pointer to the memory block regardless of whether the block was expanded.)


/* the if statement in the code ensures that the original pointer is never destroyed. */

flag fResizeMemory(void *ppv, size_t sizeNew)
{
  byte **ppb = (byte**) ppv;
  byte *pbNew;
  
  pbNew = (byte*) realloc(*ppb, sizeNew);
  if(pbNew!=NULL)
    *ppb=pbNew;
  return (pbNew!=NULL);
}

Write functions that, given valid inputs, cannot fail.

Implement standard tolower function to "return the lowercase equivalent of ch if one exist; otherwise, return the character unchanged" If you find that you can't eliminate error condition, consider disallowing the problematic cases altogether. use an assertion to verify argument.


char tolower(char ch)
{
  ASSERT(ch>='A' && ch<='Z');
  return (ch+'a'-'A');
}

Make the code intelligible at the point of call. Avoid boolean arguments.

UnsignedToStr(u, str, TRUE);

UnsignedToStr(u, str, FALSE);

#define BASE10 1

#define BASE16 0

UnsignedToStr(u, str, BASE10);

UnsignedToStr(u, str, BASE16);

void UnsignedToStr(unsigned u, char *str, unsigned base);

Write comments that emphasize potential hazards.


/* getchar -- equivalent to getc(stdin).
 *
 * getchar returns the next character from stdin. When
 * an error occurs. it returns the *int* EOF. A typical 
 * use is
 * 
 *   int ch;  //ch *must* be an int in order to hold EOF.
 * 
 *   if ((ch=getchar())!=EOF)
 *     //success
 *   else
 *     //failure
 */

int getchar*void)
...

/* realloc(pv, size)
 * ...
 * 
 * A typical use is
 * 
 *   void *pvNew;  //used to protect pv if realloc fails
 *   pvNew = realloc(pv, sizeNew);
 *   if(pvNew!=NULL)
 *   {
 *      //success --update pv
 *      pv=pvNew;
 *   }
 *   else
 *      //failure -- don't destroy pv with the NULL pvNew
 */

void *realloc(void *pv, size_t size)
...

why is the ANSI strncpy function bound to trip up the unwary programmer?
Sometimes strncpy terminates the dest str with a nul character, and sometimes it doesn't.

C++'s inline function specifier is valuable because it allows you to define functions that are as efficient as macros yet don't have the troublesome side effects that macro "functions" have in evaluating their parameters.

The serious problem with C++'s new & reference arguments is that such arguments hide the fact that you are passing the variable by reference , not by value, and that can cause confusion. For example, suppose ou redefine the fResizeMemory function so that it uses a reference argument. Programmers could then write
if( fResizeMemory(pb, sizeNew))
resize was successful
But notice, programmers unfamiliar with the function would have no reason to believe that pb might be changed during the call. How do you think that will affect program maintenance?
A related concern is that C programmers often manipulate the formal arguments to their functions because they know those arguments are passed by value, not reference But consider the maintenance programmer who fixes a bug in a function he didn't write. If that programmer fails to notice the & in the declaration he could modify the argument without realizing that the change won't be local to hide function . & reference arguments are risky because they hid an importnat implementation detail.

Mark's bookcase

Tuesday, June 10, 2014

Coders at work 2

Thursday, May 15, 2014

Coders at work 1

Sunday, September 1, 2013

The Myth of the Genius Programmer

Thursday, July 4, 2013

Writing solid code