จาก Wall Street Programmer
Advice for Newbie Wall Stree Programmers

Here’s a typical entry-level candidate with a good understanding of Computer Science, a medium grasp of C++, and absolutely no foundation in financial products:

After 2 years of working at Goldman, Morgan, Lehman, or Merrill, the candidate reaches a pretty good level of understanding of financial products He also gains a substantial amount of interoffice social skills (a result of office politics), a thorough respect for a slower than snail release process, and an anticipation of the requirement to have 2 weeks worth of meetings in order to approve an environment variable change in a configuration file. His debugging skills probably improve, but his programming skills are now completely in the toilet.

After 2 years of working at a small company, the candidate reaches a painfully thorough understanding of a small area of the financial world (whatever the company was focusing its business model on). He gains the same level of interoffice social skills (politics cannot be avoided…anywhere). He also gains excellent debugging skills by analyzing raw Solaris core dumps on a daily basis, and gains environment foundation skills by constantly tweaking Rendezvous channels, Sybase settings, Solaris process heap sizes, XML configuration files, and logging frameworks – in a live production environment (because DEV sucks everywhere…always). He gains an understanding of ‘trader-speak’ – something which will serve him greatly no matter where he goes, learns to build and deploy code to production within minutes of noticing a problem, and picks up about 4 new programming languages including C (because most API layers are in C), some shell language (because you just have to), Perl (because shell sucks), and a REALLY good understanding of SQL (using sqsh, or isql from command line).

ActiveRecord & Metaprogramming

ถ้าเราดู source code ของ ActiveRecord ใน Rails
จะเห็นว่า magic ส่วนหนึ่งของ ActiveRecord ก็มาจาก
Metaprogramming นี่เอง
ผลลัพท์ที่ได้ ต้องใช้คำว่า งามมาก
แต่ source code นี่สุดๆเลย

ลองดูว่าเขาเขียนกันอย่างไร
เริ่มด้วย Base Class ก่อน
Model ทุกตัวของเราต้อง extend Base Class นี้

module ActiveRecord
  class Base
    #... lot of instance method
    def find(*args)
      # ...
    end
    #...
  end
end

ใน base class นี้จะมี instance method อยู่เต็มเลย

เวลาเรานิยาม model ของเรา ใน rails

class Person << ActiveRecord::Base
    has_one :address    
end

ผลของ has_one ที่ใส่ลงไป
ทำให้เราสามารถ access attribute
ที่ชื่อ address ได้

p = Person.new
p.address = Address.new
p.address.line1 = 'xxxxxx'

คำถาม ก็คือ has_one มันเขียนอย่างไร
ใน ActiveRecord จะมี Module ที่เรียกว่า Association
(ซึ่งถูก include เข้าไปใน Base class)

module ActiveRecord
  module Associations
    def self.append_features(base)
      super
      base.extend(ClassMethods)
    end

    
    module ClassMethods
      def has_one(name) 
        define_method("#{name}=") { |value|
          instance_variable_set("@#{name}", value)
        }

        define_method(name)  { 
          instance_variable_get("@#{name}")
        }
      end
    end
  end
end

Magic เริ่มต้นที่ append_feature
method นี้จะถูกเรียกใช้เมื่อมีการสั่ง include ActiveRecord::Associations
พร้อมทั้งส่ง parameter มาเป็น class ที่ include method นั้น
เช่น

class Pok
    include ActiveRecord::Associations
end

parameter base ที่ append_features ได้รับ
ก็คือ Pok class นั่นเอง
จะเห็นว่า เมื่อได้รับ parameter base มา มันก็แค่สั่ง extend
ด้วย ClassMethods ต่ออีกที

magic อยู่ในส่วนนี้แหล่ะ
จะเห็นว่ามีการ define has_one ใน ClassMethods
(อันนี้ลดรูปมาให้ดูง่ายๆ code จริงๆซับซ้อนกว่านี้เยอะ)

      def has_one(name) 
        define_method("#{name}=") { |value|
          instance_variable_set("@#{name}", value)
        }

        define_method(name)  { 
          instance_variable_get("@#{name}")
        }
      end

จะเห็นว่ามีการ define method has_one ไว้
ภายในก็จะมีการเรียกใช้ define_method
เพื่อกำหนด method ที่ชื่อ address กับ address= (assigment)
การ access instance variable ก็ไม่สามารถทำได้ตรงๆ
ต้องใช้ผ่าน instance_variable_get/set

จะเห็นว่ายุ่งยากเหลือใจทีเดียว (code ของจริงเป็นสปาเก็ตตี้กว่านี้)
อ่านเพิ่มเติมได้ที่นี่

• Class are Just a Prototype Pattern
  จาก Technoblog

ทดสอบแนวคิดการจัดการ large object ด้วยการเก็บชั่วคราวบน database

วันนี้มีโจทย์เรื่อง outofmemory
กล่าวคือ มีโปรแกรมที่จำเป็นต้อง access ข้อมูลจาก text file ขนาดใหญ่
โดยทำการ parse ข้อมูลเข้ามาเป็น object model ใน memory ก่อน
จากนั้นจึงจะ parse, aggregate เป็น ข้อมูลสรุปต่อไป
ซึ่งเมื่อข้อมูลมีปริมาณสูงถึงจุดหนึ่ง ก็จะเกิด outofmemory exception

ประเด็นของการทดลองก็คือ ต้องการใช้วิธีการ parse object แบบเดิม ​
แต่ต้องการให้ memory footprint น้อยที่สุด
(ไม่สามารถเปลี่ยนให้เป็นลักษณะการ parse แบบ sequential ครั้งเดียวได้
เพราะ business logic มันบังคับอยู่)

ทางเลือกที่ทดลอง ก็คือ ถ้าเราสร้าง Wrapper ขึ้นมาห่อ object ไว้
โดย object จริงๆจะมีการ save ลง database
และ Link เข้ากับ proxy ด้วย SoftReference

public class ItemWrapper {
 private SoftReference ref;
 private int key;
 
 protected ItemWrapper(int key, Item item) {
  ref = new SoftReference(item);
 }
 
 // getter here..
 public XX getYY() {
  return getItem().getYY();
 }
 ...
 
 private Item getItem() {
  Item tmp = (Item) ref.get();
  if (tmp == null) {
   tmp = reload();
  }
  return tmp;
 }
 
 private Item reload() {
  tmp = PersistentManager.getInstance().load(key);
  ref = new SoftReference(tmp);
  return tmp;
 }
 
 
}

ถ้ามีการ access เมื่อไร ก็ check ว่า SoftReference ถูก
garbage ไปหรือยัง ถ้าถูก garbage ไปแล้ว ก็ให้ fetch ข้อมูลจาก
database ขึ้นมาใหม่

ข้อมูลที่ทดสอบคือ data ขนาด 100000 รายการ
ทดลอง implement ด้วย database 3 ตัวคือ JDBM, BerkeleyDB, MySQL

ขั้นที่ 1 ทดลองแบบ object ทั้งหมดเก็บใน memory ก่อน
ทดลองสร้างรายการ 100000 รายการ แล้วปรับค่า -Xmx จนได้ค่าเล็กสุด
ที่ไม่เกิด outofmemory
ได้ค่า footprint อยู่ที่ประมาณ 5 MB
เวลาที่ใช้ในการสร้าง items => 200 ms.


ขั้นที่ 2 ทดสอบ JDBM
การเก็บลง database ใช้วิธีนี้

 RecordManager _manager = RecordManagerFactory.createRecordManager("/tmp/pok.db");
 HTree hashtable = HTree.createInstance(_manager); 
 
  ...
 
  public void save(InternalItem item) {
    hashtable.put(new Integer(item.getKey()), item);
 count++;
 if (count > 100) {
  _manager.commit();
  count = 0;
 }
  }

ผลการทดลองพบว่าในส่วนของ JDBM มี memory footprint เพิ่มขึ้นมา
2 MB นั่นคือคราวนี้ต้องใช้ heap memory เพิ่มขึ้นเป็น 7 MB จึงจะ run ได้
เวลาที่ใช้ในการสร้าง items => 20 วินาที
(เป็นเวลาที่ tune เรื่อง group commit แล้ว)
database file => 42 MB

ขั้นที่ 3 ทดสอบ BerkleyDB
การเก็บลง DB ใช้วิธีนี้

 EnvironmentConfig ecfg = new EnvironmentConfig();
 ecfg.setAllowCreate(true);
  
 DatabaseConfig cfg = new DatabaseConfig();
 cfg.setAllowCreate(true);
 
 Environment env = new Environment(new File("/tmp/pokdb"), ecfg);
   
 Database db = env.openDatabase(null, "test.db", cfg);
 Database classDb = env.openDatabase(null, "class.db", cfg);
 StoredClassCatalog cat = new StoredClassCatalog(classDb);
 EntryBinding binding = new SerialBinding(cat, InternalItem.class);

  ...

  public void save(InternalItem item) { 
 DatabaseEntry key = new DatabaseEntry();
 DatabaseEntry entry = new DatabaseEntry();
   
 IntegerBinding.intToEntry(item.getKey(), key);
 binding.objectToEntry(item, entry);
 db.put(null, key, entry);
  }

BerkleyDB ใช้ memory เยอะสุด
ต้อง config heap ถึง 32 MB จึงจะ run ได้
เวลาที่ใช้ในการสร้าง items => 12 วินาที
database file => 22 MB

ขั้นที่ 3 ทดลองกับ MySQL
การ save ใช้ sql ผ่าน jdbc และทำเป็น preparedStatment
โดยใช้ table type เป็น MyISAM

  public void save(InternalItem item) { 
    saveStmt.setInt(1, item.getKey());
    saveStmt.setString(2, item.getDesc());
    saveStmt.setDouble(3, item.getAmount());
    saveStmt.executeUpdate();
  }

ผลการทดสอบ ต้อง config heap 7M
เวลาที่ใช้ในการสร้าง items => 27 วินาที
database file => 17 MB

สรุปผลเบื้องต้น

DBM	-Xmx	create time	file size
- (mem. only)	5M	200 ms.	-
JDBM	7M	20 sec.	42 MB
BerkleyDB	32M	12 sec.	22 MB
MySQL	7M	27 sec.	17 MB

ปัญหา
BerkleyDB ใช้ memory สูงมาก
เลยลองจับ profile ดู
พบว่ามี byte[] ค้างอยู่สูงมากๆ (91% ของทั้งหมด)
ไม่แน่ใจว่าเกิดจากการใช้ที่ไม่ถูกต้องหรือเปล่า

ส่วน JDBM นั้น ลองจับ profile แล้ว
พบว่า memory ของ SoftReference Object นั้น ใหญ่โตไม่เบาทีเดียว
คิดเป็นสัดส่วน memory ดังนี้

• SoftReference 47 %
  
• ItemWrapper 23 %
  
• byte[] 12 % (เกิดจาก HTree)
  
• Item 4.5 % (ตัวข้อมูลจริงๆ)
  

แต่ byte[] ใน JDBM ไม่ leak พอจบโปรแกรม ก็คืนหมด

ดูแล้ว SoftReference มันใหญ่เหลือเกิน
อย่างนี้มันจะช่วยประหยัด memory ได้ยังไงฟะ
หรือเราต้อง implement ReferenceQueue เพื่อ clear
SoftReference ??

Sudoku Solver in Mozart

คราวก่อนเคยเขียนเรื่อง Constraint Programming ไปแล้ว
ครั้งนั้นใช้ java

วันนี้จะลองใช้ Mozart Oz แก้ปัญหา sudoku บ้าง
เนื่องจากยังเขียน Oz ไม่เป็นเลย
ก็เลยไปลอก source code ของคนอื่นมาศึกษา
ต้นฉบับ

  Root = {Map {List.make 9}
          fun {$ Row}
      Row = {List.make 9}
      Row ::: 1#9
      {FD.distinct Row}
      Row
    end
   }

ประโยคข้างบนนี้ จะทำการสร้าง 2 Dimension Array ขนาด 9x9
ผลลัพท์ที่ได้เก็บในตัวแปร Root
fun ก็คือการ declare procedure
ส่วน fun {$ Row} => ตัว $ หมายถึง anonymous procedure

ถ้าลองเทียบเคียงกับ ruby ดู

root = Array.new(9).map {|row|
  row = Array.new(9)
}    

ส่วนที่ ruby ไม่มีก็คือ

• Row ::: 1#9
  หมายความว่า แต่ละ column สามารถเป็นได้ตั้งแต่เลข 1 ถึง 9 (domain)
  
• FD.distinct
  อันนี้เป็นประโยคที่กำหนด Constraint ใน Oz
  ความหมายก็คือ ตัวเลขในแถวเดียวกันห้ามซ้ำกัน
  

  %% All numbers in each column are distinct
  for X in 1;X=<9;X+1 do
     {FD.distinct
      {FoldR Root fun {$ Row Prev} {Nth Row X}|Prev end nil} 
     }
  end

FoldR คืออะไร
ลองเทียบกับ Ruby ดู

x = [[1,2,3],[11,12,13]].inject([]) {|prev, row|    
  prev << row[0] 
  prev 
}
x # => [1, 11]

FoldR น่าจะเทียบได้กับ Ruby Enumerable Inject
Nth ก็คือการ access array ที่ตำแหน่ง index ที่ระบุ
ส่วน | นั้น ก็คงคล้าย << ใน ruby
เพียงแต่ทิศทางจะกลับกัน << เป็นการ insert ต่อท้าย
ส่วน | เป็นการ append ข้างหน้า
Note: ถ้าเป็น lisp แล้ว | ก็คือ procedure cons นั่นเอง
(cons 1 (list 2 3 4)) => (1 2 3 4)

ถัดไปก็คือ constraint ของ 3x3 square

 %% All numbers in each 3x3 square are distinct
 for X in 0;X=<2;X+1 do
     for Y in 0;Y=<2;Y+1 do
        {FD.distinct
         {FoldR 
          {List.filterInd Root fun {$ I Row} I>=1+X*3 andthen I=<3+X*3 end}
          fun {$ Row Prev}
             {Append
              {List.filterInd Row fun {$ I Col} I>=1+Y*3 andthen I=<3+Y*3 end} 
              Prev
              }
          end
          nil
         }
        }
     end
 end

ใน ruby ไม่มี method ที่เทียบเคียงกับ filterInd
แต่ถ้าจะ implement ด้วย ruby ก็จะมีหน้าตาแบบนี้

class Array 
  def filterInd  
    tmp = []
    self.each_with_index {|elm, i|
      tmp << elm if yield i
    }
    tmp
  end
end

| กับ append ต่างกันคือ

{Show {Append [1 2 3] [5 6]}} => [1 2 3 5 6]
{Show [1 2 3] | [5 6]} => [[1 2 3] 5 6]

เทียบกับ Ruby

[1,2,3] << [5,6] # => [1,2,3,[5,6]]
[1,2,3] + [5,6] # => [1,2,3,5,6]

สุดท้าย

  %% Process specs
  {List.forAllInd Spec
   proc {$ Y R}
      Row={Nth Root Y}
   in
      {List.forAllInd R
       proc {$ X I}
          if {Not {IsFree I}} then
             {Nth Row X} :: I 
          end
       end
      }
   end
  }
  %% Search...
  {FD.distribute ff {Flatten Root}}

{Nth Row X} :: I ก็คือการระบุค่าลงไปใน
variable ตัวนั้น ว่าให้มีค่าตามโจทย์ที่ให้มา (default คือ อะไรก็ได้ที่อยู่ระหว่าง 1-9)
ส่วน FD.distribute ff ก็คือระบุให้ใช้
First Faile distribute strategy

จากการทดลอง run ได้ search graph หน้าตาแบบนี้



เวลาที่ใช้ search = 10ms (เร็วกว่าตอนทดลองใน java 8 เท่า)