2011년 7월 17일 일요일

gcc의 builtin function과 attribute

 gcc에서 사용하는 builtin function과 builtin attribute를 간단히

 정리하여 보았다.

 출처는 gcc 4.0.0의 gcc internals 문서이다. 문서에 보면 상당히 많은

 builtin function과 attribute들이 있는데 많이 사용하는

 것들만 추려보았다.

 다운로드

lucene incremental indexing

 Lucene은 증분 색인 ( incremental indexing)을 지원한다.

 incremental indexing을 하기 위해서는 기존의 인덱스와 새로 추가하는 문서들의

 인덱스를 합치는 작업을 해야하는데 이때 MergePolicy 클래스에서 이러한

 작업들의 기본 설정을 관리하게 되며 3.0.1 버전을 기준으로 봤을때

 대략 다음과 같이 3개의 Policy 클래스가 있다.

 1. LogByteSizeMergePolicy

 2. LogDocMergePolicy

 3. LogMergePolicy

 Lucene에서는 LogByteSizeMergePolicy를 기본설정으로 사용하고 있다.

 $LUENE_HOME/src/java/org/apache/lucene/index 폴더에서 이러한 Policy 클래스

 가 들어있고 IndexWriter.java의 소스를 보면 이러한 정책들이 셋팅되어 있는

 것을 확인할수 있다.



 LogByteMergePolicy의 알고리즘은

http://nlp.stanford.edu/IR-book/html/htmledition/dynamic-indexing-1.html에 잘 나와있다.


http://blog.mikemccandless.com/2011/02/visualizing-lucenes-segment-merges.html

위의 블로그에 가보면 블로그 저자가 TieredMergePolicy라는 새로운 policy를

 만들고 LUCENE-854 patch로 만들었다고 하는데 lucene-3.3.0 버전에는

 TieredMergePolicy가 포함되어 있다.

bloom filter

 석사 졸업 논문으로 위키피디아를 이용하여 검색 정확도를 향상시키는

 주제에 관하여 논문을 작성하였다.

 논문 실험에서 TREC WT10G 데이터(약 4G)를 인덱싱하는데 대략 3시간

 쯤 걸린듯하다. 내가 제안하는 알고리즘은 위키피디아의 Entry를 이용하여

 랭킹 알고리즘을 수정하였기 때문에 각 다큐먼트를 인덱싱할때에 다큐먼트의

 모든 TERM에 대해서 위키피디아의 엔트리로 존재하는지를 검색해야하고

 이때문에 초기에는 위키피디아 entry를 DB에 모두 저장하여 실험을 하여보았다.

 DB를 이용했을때 대략 WT10G 데이터 전체를 인덱싱하는데에

 10시간쯤 걸린듯 하다.

 이에 성능을 높이기 위해 bloom filter를 고려하게 되었다.

 Bloom filter는 특정 data가 존재하는지의 여부만을 알고자 할때 매우 효율적이고

 논문의 랭킹 알고리즘에서는 해당하는 TERM이 위키피디아 entry로 존재하는지

 의 여부만을 알면 되기 떄문에 굳이 DB를 사용할 필요가 없고 Bloom filter도

 이러한 목적으로는 충분하다.



 위키피디아 entry 전체( 약 700만개의 word)를  bloom filter에 저장하게 되면

 설정에 따라 다르겠지만 대략 500M정도의 메모리를 사용하게 된다.

 대신에 메모리에 직접 올라가기 떄문에 DB를 이용하는 것 보다 훨씬 빨라져서

 인덱싱하는데 대략 3시간 30분 정도 걸린듯 하다. 즉 추가적인 entry 검색으로

 30분 정도가 걸린것으로 볼수 있다. DB검색에 7시간 정도 걸린것에 비해보면

 매우 효율적이라 볼수 있다.


 내가 사용한 bloom filter의 소스를 링크한다.

 https://sites.google.com/site/wittgena/upload_file/BloomFilter.java?attredirects=0&d=1

2011년 7월 16일 토요일

linux kernel의 cache clean과 cache flush

ARM System Developer's Guide에 보면 


cache clean과 cache flush에 대해서 자세히 설명되어 있다.


flush는 cache를 그냥 비워버리고 clean은 write buffer의 데이터를


메모리에 write한 후 cache를 지운다. 


커널의 코드를 살펴보면 다음과 같다. ( 2.6.13 버젼 기준 )


static inline void flush_pmd_entry(pmd_t *pmd)
{
        const unsigned int __tlb_flag = __cpu_tlb_flags;

        if (tlb_flag(TLB_DCLEAN))
                asm("mcr        p15, 0, %0, c7, c10, 1        @ flush_pmd"
                        : : "r" (pmd) : "cc");
        if (tlb_flag(TLB_WB))
                dsb();
}

static inline void clean_pmd_entry(pmd_t *pmd)
{
        const unsigned int __tlb_flag = __cpu_tlb_flags;

        if (tlb_flag(TLB_DCLEAN))
                asm("mcr        p15, 0, %0, c7, c10, 1        @ flush_pmd"
                        : : "r" (pmd) : "cc");
}

flush 의 경우에는 


if (tlb_flag(TLB_WB)) dsb(); 


코드가 있어서 write back  캐시정책을 사용하는 경우에는


장벽을 사용해서 write buffer까지 비워버린다.
 
따라서 flush의 경우에는 캐시에서 지우게 되는 라인이 메모리에 쓰여지지 않고

clean의 경우에는 지우는 라인의 데이터가  write buffer에 남아있으므로 


메모리에 쓰여지게 되는 결과가 나타나게 된다.


정리하면 다음과 같다.



Flush
- cache를 0으로 클리어
- cache line의 유효비트를 0으로 셋팅

Clear
- cache의 dirty cache line을 메모리로 쓴 후 dirty bit를 0으로 셋팅 

stubs_offset

entry-armv.S 파일에서는 
stubs_start
       ...
stubs_end
vectors_start
       ...
vectors_end

순서로 코드가 작성되어 있는데 이를 trap_init() 함수에서는
 
memcpy((void *)vectors, __vectors_start, __vectors_end - __vectors_start);
memcpy((void *)vectors + 0x200, __stubs_start, __stubs_end - __stubs_start);


로 복사한다. 

0xffff0000 에 vectors_start 부분부터 복사해놓고
0xffff0200 에 stubs_start 부분부터 복사하게 된다. 

따라서 
                               stubs_end
stubs_start <--x--> vector_start  라고하면 stubs_offset 값은 
                     
vectors_start<--0x200--> stubs_start <--x--> stubs_end (stubs_offset의 위치)


로 바뀌게 된다.

stubs_offset 값은  __vectors_start + 0x200 - __stubs_start  = 0x200 + x 이니깐


재배치한 후의 stubs_end와 같은 위치를 가리키게 된다.

따라서 상대주소로 점프하는 b 명령어가 정상적으로 작동한다.

j2me cldc source

여러가지 J2ME CLDC에 해당하는 프로젝트들이 있지만

요즘 검색해보아도 예전 SUN에서 나온 J2ME CLDC Spec에 해당하는

KVM의 소스는 찾기가 어렵다.

이에 예전에 받아두었던 KVM 소스를 링크한다.

첨부하는 KVM 소스는 전체가 C로만 구현되어 있는 대략 8,000 라인

정도의 초경량 VM이다.

실전에 이소스를 사용할 일은 별로 없겠지만 다음의 부분들은

이해하기에는 KVM은 핵심 부분만 간결하게

구현되어 있어서 매우 유용하다.

1. garbage collection
2. interpreter
3. KNI, native method

자바 가상 머신의 핵심부분은 KVM에도 거의 모두

구현되어 있다고 보아도 무방하다. 다만 JNI대신 KNI를

사용한다던가 6개의 핵심 패키지만 포함되어 있는 부분,

ROMJavaUNIX 기능을 사용하여 KVM에 핵심 패키지를 정적 링크하는

부분 등은 SPEC에 따르는 부분이므로 조금 다르다고 볼수 있다.

문서로는 java language specification 문서나 자바 가상 머신의 이해 책을 추천한다.

























클래스의 구조와 native method, JNI, bytecode, interpreter의

작동방식을 이해하기에 두 문서는 매우 유용하다.

KVM SOURCE DOWNLOAD

lucene의 실행 script

 Lucene 소스를 다운받아 보면 소스와 라이브러리, Jar 파일만 들어있기

 때문에 처음접하는 사람의 경우 어떻게 시작해야 할지 당황하기 쉽다.

 lucene의 자매품 같은 프로젝트로 nutch가 있는데

 nutch에는 bin 폴더 밑에 "nutch"라는 실행 스크립트가 들어있다.

 이를 수정해서 lucene용 스크립트로 사용하면 많은 수정없이

 lucene에 맞게 사용할수 있다.

 다음은 nutch 스크립트를 수정해서 만든 lucene 스크립트이다.

 스크립트를 사용하려면 lucene폴더 하에 bin 폴더를 만들고

 스크립트를 lucene이라는 이름으로 저장하고 실행하면 된다.

 우선 실행하는 방법을 보자.












 bin/lucene IndexFiles [Option]과 같이 간단하게 실행할수 있다.

 보면 알겠지만 스크립트에는 contrib와 기타 jar에 포함되어 있는

 모든 main을 포함하는 클래스를 포함시켰다.

스크립트의 소스는 다음과 같다.

 #!/bin/bash

if [ $# = 0 ]; then
  echo "Usage: lucene COMMAND"
  echo "where COMMAND is one of:"
  echo "DeleteFiles"
  echo "IndexFiles"
  echo "IndexHTML"
  echo "IndexTrec"
  echo "IndexPPT"
  echo "SearchFiles"
  echo "HTMLParseTest"
  echo "PorterStemmer"
  echo "CheckIndex"
  echo "IndexReader"
  echo "QueryParser"
  echo "--------------- contrib ----------------"
  echo "PatternParser"
  echo "TernaryTree"
  echo "Benchmark"
  echo "precisionrecall"
  echo "EvaluationTrec"
  echo "programSample"
  echo "QueryDriver"
  echo "QualityQueriesFinder"
  echo "ExtractReuters"
  echo "ExtractWikipedia"
  echo "SanityLoadLibrary"
  echo "FieldTermStack"
  echo "Lucli"
  echo "FieldNormModifier"
  echo "IndexSplitter"
  echo "MultiPassIndexSplitter"
  echo "HighFreqTerms"
  echo "IndexMergeTool"
  echo "PrecedenceQueryParser"
  echo "MoreLikeThis"
  echo "RemoteSearchable"
  echo "TestRemoteSort"
  echo "SnowballTestApp"
  echo "GeoHashUtils"
  echo "ListSearcherSimulater"
  echo "SynExpand"
  echo "SynLookup"
  echo "Syns2Index"
  echo "or"
  echo " CLASSNAME                  run the class named CLASSNAME"
  exit 1
fi

# get arguments
COMMAND=$1
shift

# some directories
THIS_DIR=`dirname "$THIS"`
#LUCENE_HOME=`cd "$THIS_DIR/.." ; pwd`
LUCENE_HOME=`echo $LUCENE_HOME`

# some Java parameters
if [ "$LUCENE_JAVA_HOME" != "" ]; then
  #echo "run java in $LUCENE_JAVA_HOME"
  JAVA_HOME=$LUCENE_JAVA_HOME
fi

if [ "$JAVA_HOME" = "" ]; then
  echo "Error: JAVA_HOME is not set."
  exit 1
fi

JAVA=$JAVA_HOME/bin/java
JAVA_HEAP_MAX=-Xmx1000m

# check envvars which might override default args
if [ "$LUCENE_HEAPSIZE" != "" ]; then
  #echo "run with heapsize $LUCENE_HEAPSIZE"
  JAVA_HEAP_MAX="-Xmx""$LUCENE_HEAPSIZE""m"
  #echo $JAVA_HEAP_MAX
fi

CLASSPATH=$LUCENE_HOME/build/lucene-core-3.0.1-dev.jar:$LUCENE_HOME/build/lucene-demos-3.0.1-dev.jar
CLASSPATH=${CLASSPATH}:$JAVA_HOME/lib/tools.jar
#CLASSPATH=${CLASSPATH}:$LUCENE_HOME/build/classes

# add contrib to classpath
#for f in $LUCENE_HOME/build/lib-contrib/*.jar; do
#  CLASSPATH=${CLASSPATH}:$f;
#done

# add libs to CLASSPATH
for f in $LUCENE_HOME/lib/*.jar; do
  CLASSPATH=${CLASSPATH}:$f;
done

if [ "x$JAVA_LIBRARY_PATH" != "x" ]; then
  LUCENE_OPTS="$LUCENE_OPTS -Djava.library.path=$JAVA_LIBRARY_PATH"
fi

# figure out which class to run
if [ "$COMMAND" = "DeleteFiles" ] ; then
    CLASS=org.apache.lucene.demo.DeleteFiles
elif [ "$COMMAND" = "IndexFiles" ] ; then
    CLASS=org.apache.lucene.demo.IndexFiles
elif [ "$COMMAND" = "IndexHTML" ] ; then
    CLASS=org.apache.lucene.demo.IndexHTML
elif [ "$COMMAND" = "IndexTrec" ] ; then
    CLASS=kr.ac.kaist.demo.IndexTrec
    #CLASS=org.apache.lucene.demo.IndexTrec
elif [ "$COMMAND" = "SearchFiles" ] ; then
    CLASS=kr.ac.kaist.demo.SearchFiles
elif [ "$COMMAND" = "HTMLParseTest" ] ; then
    CLASS=org.apache.lucene.demo.html.Test
elif [ "$COMMAND" = "PorterStemmer" ] ; then
    CLASS=org.apache.lucene.analysis.PorterStemmer
elif [ "$COMMAND" = "CheckIndex" ] ; then
    CLASS=org.apache.lucene.index.CheckIndex
elif [ "$COMMAND" = "IndexReader" ] ; then
    CLASS=org.apache.lucene.IndexReader
elif [ "$COMMAND" = "QueryParser" ] ; then
    CLASS=org.apache.lucene.queryParser.QueryParser
elif [ "$COMMAND" = "English" ] ; then
    CLASS=org.apache.lucene.util.English
elif [ "$COMMAND" = "PatternParser" ] ; then
    CLASS=org.apache.lucene.analysis.compound.hyphenation.PatternParser
elif [ "$COMMAND" = "TernaryTree" ] ; then
    CLASS=org.apache.lucene.analysis.compound.hyphenation.TernaryTree
elif [ "$COMMAND" = "Benchmark" ] ; then
    CLASS=org.apache.lucene.benchmark.byTask.Benchmark
elif [ "$COMMAND" = "precisionrecall" ] ; then
    CLASS=kr.ac.kaist.demo.PrecisionRecall
elif [ "$COMMAND" = "EvaluationTrec" ] ; then
    CLASS=kr.ac.kaist.demo.EvaluationTrec
elif [ "$COMMAND" = "programSample" ] ; then
    CLASS=org.apache.lucene.benchmark.byTask.programmatic.Sample
elif [ "$COMMAND" = "QueryDriver" ] ; then
    CLASS=org.apache.lucene.benchmark.quality.trec.QueryDriver
elif [ "$COMMAND" = "QualityQueriesFinder" ] ; then
    CLASS=org.apache.lucene.benchmark.quality.utils.QualityQueriesFinder
elif [ "$COMMAND" = "ExtractReuters" ] ; then
    CLASS=org.apache.lucene.benchmark.utils.ExtractWikipedia
elif [ "$COMMAND" = "ExtractWikipedia" ] ; then
    CLASS=org.apache.lucene.benchmark.utils.ExtractWikipedia
elif [ "$COMMAND" = "SanityLoadLibrary" ] ; then
    CLASS=org.apache.lucene.store.db.SanityLoadLibrary
elif [ "$COMMAND" = "FieldTermStack" ] ; then
    CLASS=org.apache.lucene.search.vectorhighlight.FieldTermStack
elif [ "$COMMAND" = "Lucli" ] ; then
    CLASS=lucli.Lucli
elif [ "$COMMAND" = "FieldNormModifier" ] ; then
    CLASS=org.apache.lucene.index.FieldNormModifier
elif [ "$COMMAND" = "IndexSplitter" ] ; then
    CLASS=org.apache.lucene.index.IndexSplitter
elif [ "$COMMAND" = "MultiPassIndexSplitter" ] ; then
    CLASS=org.apache.lucene.index.MultiPassIndexSplitter
elif [ "$COMMAND" = "HighFreqTerms" ] ; then
    CLASS=org.apache.lucene.misc.HighFreqTerms
elif [ "$COMMAND" = "IndexMergeTool" ] ; then
    CLASS=org.apache.lucene.misc.IndexMergeTool
elif [ "$COMMAND" = "PrecedenceQueryParser" ] ; then
    CLASS=org.apache.lucene.
elif [ "$COMMAND" = "MoreLikeThis" ] ; then
    CLASS=org.apache.lucene.search.similar.MoreLikeThis
elif [ "$COMMAND" = "RemoteSearchable" ] ; then
    CLASS=org.apache.lucene.search.RemoteSearchable
elif [ "$COMMAND" = "TestRemoteSort" ] ; then
    CLASS=org.apache.lucene.search.TestRemoteSort
elif [ "$COMMAND" = "SnowballTestApp" ] ; then
    CLASS=org.tartarus.snowball.TestApp
elif [ "$COMMAND" = "GeoHashUtils" ] ; then
    CLASS=org.apache.lucene.spatial.geohash.GeoHashUtils
elif [ "$COMMAND" = "ListSearcherSimulater" ] ; then
    CLASS=org.apache.lucene.swing.models.ListSearcherSimulator
elif [ "$COMMAND" = "SynExpand" ] ; then
    CLASS=org.apache.lucene.wordnet.SynExpand
elif [ "$COMMAND" = "SynLookup" ] ; then
    CLASS=org.apache.lucene.wordnet.SynLookup
elif [ "$COMMAND" = "Syns2Index" ] ; then
    CLASS=org.apache.lucene.wordnet.Syns2Index
else
  CLASS=$COMMAND
fi

exec "$JAVA" $JAVA_HEAP_MAX $LUCENE_OPTS -cp "$CLASSPATH" $CLASS "$@"