# HG changeset patch # User Daichi TOMA # Date 1379014395 -32400 # Node ID 426856180cc3c78bf57a7019c4bfed3a522642df # Parent cbb44aa8867b73ce5c88b48ea313841cd0053123 rework this slides diff -r cbb44aa8867b -r 426856180cc3 Slides/images/nodepath.graffle --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/Slides/images/nodepath.graffle Fri Sep 13 04:33:15 2013 +0900 @@ -0,0 +1,1411 @@ + + + + + ActiveLayerIndex + 0 + ApplicationVersion + + com.omnigroup.OmniGrafflePro + 139.17.0.185490 + + AutoAdjust + + BackgroundGraphic + + Bounds + {{0, 0}, {558.99997329711914, 783}} + Class + SolidGraphic + ID + 2 + Style + + shadow + + Draws + NO + + stroke + + Draws + NO + + + + BaseZoom + 0 + CanvasOrigin + {0, 0} + ColumnAlign + 1 + ColumnSpacing + 36 + CreationDate + 2013-02-11 06:47:37 +0000 + Creator + shoshi + DisplayScale + 1 0/72 in = 1.0000 in + GraphDocumentVersion + 8 + GraphicsList + + + Bounds + {{279.49998664855957, 139}, {144, 27}} + Class + ShapedGraphic + FitText + YES + Flow + Resize + ID + 60 + Shape + Rectangle + Style + + fill + + Draws + NO + + shadow + + Draws + NO + + stroke + + Draws + NO + + + Text + + Pad + 0 + Text + {\rtf1\ansi\ansicpg1252\cocoartf1187\cocoasubrtf390 +\cocoascreenfonts1{\fonttbl\f0\fnil\fcharset0 Ricty-Regular;} +{\colortbl;\red255\green255\blue255;} +\pard\tx560\tx1120\tx1680\tx2240\tx2800\tx3360\tx3920\tx4480\tx5040\tx5600\tx6160\tx6720\pardirnatural\qc + +\f0\fs48 \cf0 Path [1,2,3]} + VerticalPad + 0 + + Wrap + NO + + + Bounds + {{241.5, 254}, {80, 30}} + Class + ShapedGraphic + FitText + YES + Flow + Resize + FontInfo + + Font + HiraKakuProN-W3 + Size + 20 + + ID + 57 + Shape + Rectangle + Style + + shadow + + Draws + NO + + stroke + + Draws + NO + Width + 3 + + + Text + + Pad + 0 + Text + {\rtf1\ansi\ansicpg1252\cocoartf1187\cocoasubrtf390 +\cocoascreenfonts1{\fonttbl\f0\fnil\fcharset128 HiraKakuProN-W3;} +{\colortbl;\red255\green255\blue255;} +\pard\tx560\tx1120\tx1680\tx2240\tx2800\tx3360\tx3920\tx4480\tx5040\tx5600\tx6160\tx6720\pardirnatural\qc + +\f0\fs40 \cf0 \'95\'d2\'8f\'57\'91\'ce\'8f\'db} + VerticalPad + 0 + + Wrap + NO + + + Bounds + {{225, 216.49299491436881}, {45, 43}} + Class + ShapedGraphic + FontInfo + + Font + HiraKakuProN-W3 + Size + 20 + + ID + 52 + Shape + Circle + Style + + shadow + + Draws + NO + + stroke + + Color + + b + 0 + g + 0 + r + 1 + + GapRatio + 0.5 + Width + 8 + + + Text + + Text + {\rtf1\ansi\ansicpg1252\cocoartf1187\cocoasubrtf390 +\cocoascreenfonts1{\fonttbl\f0\fswiss\fcharset0 Helvetica;} +{\colortbl;\red255\green255\blue255;} +\pard\tx560\tx1120\tx1680\tx2240\tx2800\tx3360\tx3920\tx4480\tx5040\tx5600\tx6160\tx6720\pardirnatural\qc + +\f0\fs40 \cf0 3} + VerticalPad + 0 + + + + Bounds + {{164, 216.49299491436881}, {45, 43}} + Class + ShapedGraphic + FontInfo + + Font + HiraKakuProN-W3 + Size + 20 + + ID + 51 + Shape + Circle + Style + + fill + + Draws + NO + + shadow + + Draws + NO + + stroke + + Width + 3 + + + Text + + Text + {\rtf1\ansi\ansicpg1252\cocoartf1187\cocoasubrtf390 +\cocoascreenfonts1{\fonttbl\f0\fswiss\fcharset0 Helvetica;} +{\colortbl;\red255\green255\blue255;} +\pard\tx560\tx1120\tx1680\tx2240\tx2800\tx3360\tx3920\tx4480\tx5040\tx5600\tx6160\tx6720\pardirnatural\qc + +\f0\fs40 \cf0 2} + VerticalPad + 0 + + + + Bounds + {{103, 216.49299491436881}, {45, 43}} + Class + ShapedGraphic + FontInfo + + Font + HiraKakuProN-W3 + Size + 20 + + ID + 50 + Shape + Circle + Style + + shadow + + Draws + NO + + stroke + + Width + 3 + + + Text + + Text + {\rtf1\ansi\ansicpg1252\cocoartf1187\cocoasubrtf390 +\cocoascreenfonts1{\fonttbl\f0\fswiss\fcharset0 Helvetica;} +{\colortbl;\red255\green255\blue255;} +\pard\tx560\tx1120\tx1680\tx2240\tx2800\tx3360\tx3920\tx4480\tx5040\tx5600\tx6160\tx6720\pardirnatural\qc + +\f0\fs40 \cf0 1} + VerticalPad + 0 + + + + Bounds + {{42, 216.49299491436881}, {45, 43}} + Class + ShapedGraphic + FontInfo + + Font + HiraKakuProN-W3 + Size + 20 + + ID + 49 + Shape + Circle + Style + + shadow + + Draws + NO + + stroke + + Width + 3 + + + Text + + Text + {\rtf1\ansi\ansicpg1252\cocoartf1187\cocoasubrtf390 +\cocoascreenfonts1{\fonttbl\f0\fswiss\fcharset0 Helvetica;} +{\colortbl;\red255\green255\blue255;} +\pard\tx560\tx1120\tx1680\tx2240\tx2800\tx3360\tx3920\tx4480\tx5040\tx5600\tx6160\tx6720\pardirnatural\qc + +\f0\fs40 \cf0 0} + VerticalPad + 0 + + + + Bounds + {{189, 148.50700508563119}, {45, 43}} + Class + ShapedGraphic + FontInfo + + Font + HiraKakuProN-W3 + Size + 20 + + ID + 44 + Shape + Circle + Style + + shadow + + Draws + NO + + stroke + + Width + 3 + + + Text + + Text + {\rtf1\ansi\ansicpg1252\cocoartf1187\cocoasubrtf390 +\cocoascreenfonts1{\fonttbl\f0\fswiss\fcharset0 Helvetica;} +{\colortbl;\red255\green255\blue255;} +\pard\tx560\tx1120\tx1680\tx2240\tx2800\tx3360\tx3920\tx4480\tx5040\tx5600\tx6160\tx6720\pardirnatural\qc + +\f0\fs40 \cf0 3} + VerticalPad + 0 + + + + Bounds + {{128, 148.50700508563119}, {45, 43}} + Class + ShapedGraphic + FontInfo + + Font + HiraKakuProN-W3 + Size + 20 + + ID + 43 + Shape + Circle + Style + + fill + + Draws + NO + + shadow + + Draws + NO + + stroke + + Color + + b + 0 + g + 0 + r + 1 + + GapRatio + 0.5 + Width + 8 + + + Text + + Text + {\rtf1\ansi\ansicpg1252\cocoartf1187\cocoasubrtf390 +\cocoascreenfonts1{\fonttbl\f0\fswiss\fcharset0 Helvetica;} +{\colortbl;\red255\green255\blue255;} +\pard\tx560\tx1120\tx1680\tx2240\tx2800\tx3360\tx3920\tx4480\tx5040\tx5600\tx6160\tx6720\pardirnatural\qc + +\f0\fs40 \cf0 2} + VerticalPad + 0 + + + + Bounds + {{67, 148.50700508563119}, {45, 43}} + Class + ShapedGraphic + FontInfo + + Font + HiraKakuProN-W3 + Size + 20 + + ID + 42 + Shape + Circle + Style + + shadow + + Draws + NO + + stroke + + Width + 3 + + + Text + + Text + {\rtf1\ansi\ansicpg1252\cocoartf1187\cocoasubrtf390 +\cocoascreenfonts1{\fonttbl\f0\fswiss\fcharset0 Helvetica;} +{\colortbl;\red255\green255\blue255;} +\pard\tx560\tx1120\tx1680\tx2240\tx2800\tx3360\tx3920\tx4480\tx5040\tx5600\tx6160\tx6720\pardirnatural\qc + +\f0\fs40 \cf0 1} + VerticalPad + 0 + + + + Bounds + {{6, 148.50700508563119}, {45, 43}} + Class + ShapedGraphic + FontInfo + + Font + HiraKakuProN-W3 + Size + 20 + + ID + 41 + Shape + Circle + Style + + shadow + + Draws + NO + + stroke + + Width + 3 + + + Text + + Text + {\rtf1\ansi\ansicpg1252\cocoartf1187\cocoasubrtf390 +\cocoascreenfonts1{\fonttbl\f0\fswiss\fcharset0 Helvetica;} +{\colortbl;\red255\green255\blue255;} +\pard\tx560\tx1120\tx1680\tx2240\tx2800\tx3360\tx3920\tx4480\tx5040\tx5600\tx6160\tx6720\pardirnatural\qc + +\f0\fs40 \cf0 0} + VerticalPad + 0 + + + + Class + LineGraphic + FontInfo + + Font + HiraKakuProN-W3 + Size + 20 + + Head + + ID + 33 + + ID + 37 + Points + + {160.91934706375142, 48.51562474572264} + {217.12774085404706, 87.919447196651547} + + Style + + stroke + + HeadArrow + 0 + Legacy + + TailArrow + 0 + Width + 3 + + + Tail + + ID + 28 + + + + Class + LineGraphic + FontInfo + + Font + HiraKakuProN-W3 + Size + 20 + + Head + + ID + 32 + + ID + 36 + Points + + {151.53097247771751, 56.225170235688623} + {165.34057841889111, 82.309981457905437} + + Style + + stroke + + HeadArrow + 0 + Legacy + + TailArrow + 0 + Width + 3 + + + Tail + + ID + 28 + + + + Class + LineGraphic + FontInfo + + Font + HiraKakuProN-W3 + Size + 20 + + Head + + ID + 30 + + ID + 34 + Points + + {119.026356278511, 49.688462477456426} + {72.012604765620722, 86.862126464392929} + + Style + + stroke + + HeadArrow + 0 + Legacy + + TailArrow + 0 + Width + 3 + + + Tail + + ID + 28 + + + + Bounds + {{214, 80}, {45, 43}} + Class + ShapedGraphic + FontInfo + + Font + HiraKakuProN-W3 + Size + 20 + + ID + 33 + Shape + Circle + Style + + shadow + + Draws + NO + + stroke + + Width + 3 + + + Text + + Text + {\rtf1\ansi\ansicpg1252\cocoartf1187\cocoasubrtf390 +\cocoascreenfonts1{\fonttbl\f0\fswiss\fcharset0 Helvetica;} +{\colortbl;\red255\green255\blue255;} +\pard\tx560\tx1120\tx1680\tx2240\tx2800\tx3360\tx3920\tx4480\tx5040\tx5600\tx6160\tx6720\pardirnatural\qc + +\f0\fs40 \cf0 n} + VerticalPad + 0 + + + + Bounds + {{153, 80}, {45, 43}} + Class + ShapedGraphic + FontInfo + + Font + HiraKakuProN-W3 + Size + 20 + + ID + 32 + Shape + Circle + Style + + fill + + Draws + NO + + shadow + + Draws + NO + + stroke + + Draws + NO + Width + 3 + + + Text + + Text + {\rtf1\ansi\ansicpg1252\cocoartf1187\cocoasubrtf390 +\cocoascreenfonts1{\fonttbl\f0\fswiss\fcharset0 Helvetica;} +{\colortbl;\red255\green255\blue255;} +\pard\tx560\tx1120\tx1680\tx2240\tx2800\tx3360\tx3920\tx4480\tx5040\tx5600\tx6160\tx6720\pardirnatural\qc + +\f0\fs40 \cf0 ...} + VerticalPad + 0 + + + + Bounds + {{92, 80}, {45, 43}} + Class + ShapedGraphic + FontInfo + + Font + HiraKakuProN-W3 + Size + 20 + + ID + 31 + Shape + Circle + Style + + shadow + + Draws + NO + + stroke + + Color + + b + 0 + g + 0 + r + 1 + + GapRatio + 0.5 + Width + 8 + + + Text + + Text + {\rtf1\ansi\ansicpg1252\cocoartf1187\cocoasubrtf390 +\cocoascreenfonts1{\fonttbl\f0\fswiss\fcharset0 Helvetica;} +{\colortbl;\red255\green255\blue255;} +\pard\tx560\tx1120\tx1680\tx2240\tx2800\tx3360\tx3920\tx4480\tx5040\tx5600\tx6160\tx6720\pardirnatural\qc + +\f0\fs40 \cf0 1} + VerticalPad + 0 + + + + Bounds + {{31, 80}, {45, 43}} + Class + ShapedGraphic + FontInfo + + Font + HiraKakuProN-W3 + Size + 20 + + ID + 30 + Shape + Circle + Style + + shadow + + Draws + NO + + stroke + + Width + 3 + + + Text + + Text + {\rtf1\ansi\ansicpg1252\cocoartf1187\cocoasubrtf390 +\cocoascreenfonts1{\fonttbl\f0\fswiss\fcharset0 Helvetica;} +{\colortbl;\red255\green255\blue255;} +\pard\tx560\tx1120\tx1680\tx2240\tx2800\tx3360\tx3920\tx4480\tx5040\tx5600\tx6160\tx6720\pardirnatural\qc + +\f0\fs40 \cf0 0} + VerticalPad + 0 + + + + Bounds + {{117, 12}, {45, 43}} + Class + ShapedGraphic + FontInfo + + Font + HiraKakuProN-W3 + Size + 20 + + ID + 28 + Shape + Circle + Style + + shadow + + Draws + NO + + stroke + + Color + + b + 0 + g + 0 + r + 1 + + GapRatio + 0.5 + Width + 8 + + + Text + + Pad + 0 + Text + {\rtf1\ansi\ansicpg1252\cocoartf1187\cocoasubrtf390 +\cocoascreenfonts1{\fonttbl\f0\fswiss\fcharset0 Helvetica;} +{\colortbl;\red255\green255\blue255;} +\pard\tx560\tx1120\tx1680\tx2240\tx2800\tx3360\tx3920\tx4480\tx5040\tx5600\tx6160\tx6720\pardirnatural\qc + +\f0\fs40 \cf0 root} + VerticalPad + 0 + + + + Class + LineGraphic + FontInfo + + Font + HiraKakuProN-W3 + Size + 20 + + Head + + ID + 52 + + ID + 56 + Points + + {169.05305440841548, 183} + {226.08055294180772, 222.97750215991132} + + Style + + stroke + + Color + + b + 0 + g + 0 + r + 1 + + GapRatio + 0.5 + HeadArrow + 0 + Legacy + + TailArrow + 0 + Width + 8 + + + + + Class + LineGraphic + FontInfo + + Font + HiraKakuProN-W3 + Size + 20 + + Head + + ID + 51 + + ID + 55 + Points + + {160.8745931692697, 189.63399464199267} + {175.63079338204193, 217.4811658038935} + + Style + + stroke + + HeadArrow + 0 + Legacy + + TailArrow + 0 + Width + 3 + + + + + Class + LineGraphic + FontInfo + + Font + HiraKakuProN-W3 + Size + 20 + + Head + + ID + 50 + + ID + 54 + Points + + {142.81004419374304, 190.73205310302325} + {133.45022918245274, 216.28679274796559} + + Style + + stroke + + HeadArrow + 0 + Legacy + + TailArrow + 0 + Width + 3 + + + + + Class + LineGraphic + FontInfo + + Font + HiraKakuProN-W3 + Size + 20 + + Head + + ID + 49 + + ID + 53 + Points + + {132.76672715531757, 184.00476228664814} + {83.01122904480259, 223.3535273209971} + + Style + + stroke + + HeadArrow + 0 + Legacy + + TailArrow + 0 + Width + 3 + + + + + Class + LineGraphic + FontInfo + + Font + HiraKakuProN-W3 + Size + 20 + + Head + + ID + 44 + + ID + 48 + Points + + {133.05305440841548, 115.01401017126238} + {192.12764986372164, 156.4265712715451} + + Style + + stroke + + HeadArrow + 0 + Legacy + + TailArrow + 0 + Width + 3 + + + + + Class + LineGraphic + FontInfo + + Font + HiraKakuProN-W3 + Size + 20 + + Head + + ID + 42 + + ID + 46 + Points + + {106.31004419374304, 123.24606327428563} + {97.31885091607414, 148.25710196198463} + + Style + + stroke + + HeadArrow + 0 + Legacy + + TailArrow + 0 + Width + 3 + + + + + Class + LineGraphic + FontInfo + + Font + HiraKakuProN-W3 + Size + 20 + + Head + + ID + 41 + + ID + 45 + Points + + {96.766727155317568, 116.01877245791053} + {47.011229044802548, 155.36753749225949} + + Style + + stroke + + HeadArrow + 0 + Legacy + + TailArrow + 0 + Width + 3 + + + + + Class + LineGraphic + FontInfo + + Font + HiraKakuProN-W3 + Size + 20 + + Head + + ID + 31 + + ID + 35 + Points + + {130.66041554065748, 57.543669730540152} + {123.33958446038726, 77.456330269809754} + + Style + + stroke + + Color + + b + 0 + g + 0 + r + 1 + + GapRatio + 0.5 + HeadArrow + 0 + Legacy + + TailArrow + 0 + Width + 8 + + + Tail + + ID + 28 + + + + Class + LineGraphic + FontInfo + + Font + HiraKakuProN-W3 + Size + 20 + + Head + + ID + 43 + + ID + 47 + Points + + {124.8745931692697, 121.64800481325506} + {138.46023269886561, 147.28615175280976} + + Style + + stroke + + Color + + b + 0 + g + 0 + r + 1 + + GapRatio + 0.5 + HeadArrow + 0 + Legacy + + TailArrow + 0 + Width + 8 + + + + + GridInfo + + GuidesLocked + NO + GuidesVisible + YES + HPages + 1 + ImageCounter + 1 + KeepToScale + + Layers + + + Lock + NO + Name + レイヤー 1 + Print + YES + View + YES + + + LayoutInfo + + Animate + NO + circoMinDist + 18 + circoSeparation + 0.0 + layoutEngine + dot + neatoSeparation + 0.0 + twopiSeparation + 0.0 + + LinksVisible + NO + MagnetsVisible + NO + MasterSheets + + ModificationDate + 2013-09-12 18:32:54 +0000 + Modifier + Daichi TOMA + NotesVisible + NO + Orientation + 2 + OriginVisible + NO + PageBreaks + YES + PrintInfo + + NSBottomMargin + + float + 41 + + NSHorizonalPagination + + coded + BAtzdHJlYW10eXBlZIHoA4QBQISEhAhOU051bWJlcgCEhAdOU1ZhbHVlAISECE5TT2JqZWN0AIWEASqEhAFxlwCG + + NSLeftMargin + + float + 18 + + NSPaperSize + + size + {594.99997329711914, 842} + + NSPrintReverseOrientation + + int + 0 + + NSRightMargin + + float + 18 + + NSTopMargin + + float + 18 + + + PrintOnePage + + ReadOnly + NO + RowAlign + 1 + RowSpacing + 36 + SheetTitle + キャンバス 1 + SmartAlignmentGuidesActive + YES + SmartDistanceGuidesActive + YES + UniqueID + 1 + UseEntirePage + + VPages + 1 + WindowInfo + + CurrentSheet + 0 + ExpandedCanvases + + Frame + {{96, 86}, {1162, 922}} + ListView + + OutlineWidth + 142 + RightSidebar + + ShowRuler + + Sidebar + + SidebarWidth + 120 + VisibleRegion + {{0, 0}, {513.5, 391.5}} + Zoom + 2 + ZoomValues + + + キャンバス 1 + 2 + 1 + + + + + diff -r cbb44aa8867b -r 426856180cc3 Slides/images/nodepath.png Binary file Slides/images/nodepath.png has changed diff -r cbb44aa8867b -r 426856180cc3 Slides/jssst.html --- a/Slides/jssst.html Thu Sep 12 14:57:01 2013 +0900 +++ b/Slides/jssst.html Fri Sep 13 04:33:15 2013 +0900 @@ -42,9 +42,8 @@ Haskellによる非破壊的木構造を用いたCMSの実装

- Daichi TOMA -
- Sep 13, 2013 + Daichi TOMA
+ Sep 13, 2013

-
-

- はじめに - -

+

Haskellによるデータベースの実装

- 本研究室では非破壊的木構造データベース Jungle の開発を行っている。 - 非破壊的木構造は、通常の木構造と違い、木構造自体を破壊せずに編集を行うことが可能である。 + ウェブサービスの利用者の増加の予想は困難である。 + ウェブサービスは、負荷が増大した際に容易に拡張できるスケーラビリティがあることが望ましい。

- Jungle には、既に Java による実装があるが、本研究ではHaskellによる再実装を行った。 + ウェブサービスのスケーラビリティの実現のネックは、データベースである。 + 本研究室では、スケーラビリティのあるデータベースとして Jungle を開発している。 + Jungle には、既に Java による実装があり、分散データベース Cassandra 以上の性能が確認できるなどの成果がでている。 +

+

+ 本研究では、Haskell による Jungle の再実装を行った。 その結果、Java 版と同程度の性能を得ることができた。また、Java 版の実装と比較し、開発期間及びコード行数の短縮ができた。

-

- Haskell -

-

- - Haskell は、純粋関数型プログラミング言語である。 - 変数への代入は一度のみで、書き換えることはできない。 -

-

- 非破壊的木構造は変数への代入が発生しないことから、関数型言語と相性が良いと考えられる。 - そのため、Haskell を用いて再実装を行った。 -

-
- -
-

- 非破壊的木構造データベース Jungle -

-

- 非破壊的木構造を取り扱うデータベースである。 - 既に Java による実装が存在する。 -

- +

非破壊的木構造データベース Jungle

- 特徴を以下に示す。 -

-

-
- -
-

- 破壊的木構造 -

- - -

- ロックを行わなければ、参照中に他の編集者が編集してしまうと、整合性がなくなってしまう。 -

-

-

- -
-

-
- -
-

- 非破壊的木構造 -

- -

- 参照中に他の編集者が編集してしまっても、整合性がなくなることはない。 + Jungle は、非破壊的木構造を取り扱うデータベースである。 + 非破壊的木構造は、元の木構造を書き換えることなく、編集を行うことが可能である。

@@ -214,51 +138,101 @@
-

- 非破壊的木構造の特徴 -

+

非破壊的木構造の特徴

- 非破壊的木構造は、破壊的木構造と異なり以下の利点がある。 + 非破壊的木構造は以下の特徴を持つ。

- ロックを必要とせず、自由にコピーを行えるため、スケーラブルなシステムに有用である。 - + ロックを必要とせず、また破壊されることがないため、自由にコピーを作成することができる。 + コピーを複数作成することで、アクセスを分散させることが可能であり、スケーラビリティが確保できる。 +

+

+ この非破壊的木構造を取り扱うデータベースが Jungle である。

-

- 非破壊的木構造データベース Jungle -

+

非破壊的木構造データベース Jungle

+

+ Jungle は複数の木を保持することができる。 + それぞれの木には名前がついており、名前を用いることで最新のルートノードへアクセスすることができる。 +

+

+ 木のノードには、属性と属性値の組がある。 + また、順序のある子ノードを持つ。 +

+

+ ノードの属性と属性値、子ノードは編集可能である。 + 編集には、ルートノードと編集するノードへのパスによって行われる。 + 編集すると新しい木が作成される。 +

+

+ 最新版は、サーバ毎に異なる可能性がある。 + 木へのアクセスは並行して行われ、競合したアクセスはマージにより解決される +

+

+ 本研究では、Haskell による Jungle の再実装を行った。 +

+
+ +
+

Haskell で実装する利点

+

+ 非破壊的木構造は、破壊的な代入のない Haskell と相性がよいと考えられる。 + Haskell は、破壊的な代入許さず、参照透過性を持つ。 +

- + 参照透過性を持つため、ソースコードは明瞭となる。 + また、どのようなタイミングで評価しても結果は同じとなるため、並行に評価することができる。 +

+

+ Haskell は定理証明支援系との相性がよく、信頼性の高いシステムソフトウェアができる可能性がある +

+
+ +
+

コード行数及び開発期間の短縮

+

+ Haskell では、再帰的なデータ構造を定義することが可能で、木構造がデータ型として定義できる。 + また、パターンマッチにより、シンプルに場合分けをすることが可能である。 + そのため、コード行数を短くすることが可能で、開発期間の短縮にも繋がった。 +

+

+ Java 版の Jungle の実装と比較すると、コード行数は約 3000 行から約 150 行へ短くなった。 + また開発期間は Java 版の実装で、3 ヶ月程度かかったが、 Haskell 版の実装は 2 週間程度であった。 +

+
+ +
+

Haskell 版 Jungle の API

+

+ Jungle は、様々なシステムに組み込んで使用できる。 + Haskell 版 Jungle の利用方法について述べる。 +

+ +
+

木の作成

+

Jungle は複数の木を保持することができる。 - 木には名前がついており、名前を利用して判別を行う。 - 作成・編集・削除を行うことができる。 + 木には名前がついており、名前を利用して、木構造の取得や削除を行うことができる。 

 jungle = createJungle
 new_jung = createTree jungle "new_tree"

- createTree 関数を利用して木構造を作成する。 + createTree 関数を利用して、"new_tree"という名前の木構造を作成するコードである。

-

- 非破壊的木構造データベース Jungle -

+

ルートノードの取得

- 木構造とルートノードを取得するためには以下のように記述する。 + ルートノードを取得するためには以下のように記述する。 

 tree = getTreeByName new_jung "new_tree"
@@ -267,75 +241,48 @@
         

         getTreeByName 関数で名前を指定することで木構造を取得できる。
         getRootNode 関数でルートノードを取得できる。
-
+        

+
+ +
+

子の追加及び属性の追加

+

+ addNewChildAt 関数で、ノードに新しい子を追加することができる。 + また、putAttribute 関数で、ノードに属性を追加できる。 +

+
+new_tree = addNewChildAt tree [0,1] 0
+new_tree2 = putAttribute new_tree [0,1,0] "key" "value"
+
+

+ どのノードを編集するかという情報は、ルートノードからのパスを渡すことで解決する。

-

- 非破壊的木構造データベース Jungle -

+

パス

- addNewChildAt 関数で、ノードに新しい子を追加することができる。 - また、putAttribute 関数で、ノードが持つ連想リストを編集できる。 + パスは Haskell のリストとして定義する。 + ルートノードからスタートし、ノードの子供の場所を次々に指定していくことで編集対象のノードの場所を表す。

- - どのノードを編集するかという情報は、ルートノードからのパスを渡すことで解決する。 - 木を編集したあと、updateTree 関数を用いて既存の Jungle に変更を加え新しい Jungle を作成する。 -

-
-new_tree = addNewChildAt tree [0,1] 0
-new_tree2 = putAttribute new_tree
-                 [0,1,0] "key" "value"
-new_jungle = updateTree jungle new_tree2
-
-
- -
-

- 非破壊的木構造データベース Jungle -

-

- 非破壊的木構造であっても、どのノードが最新のルートノードなのかという情報が必要である。 - スレッドセーフに取り扱う必要があるため、Haskell のソフトウェア・トランザクショナル・メモリを用いて管理している。 - +

+ +

-o -

- 開発期間の短縮 -

+

ベンチマーク

- Java 版の Jungle の実装と比較すると、コード行数は約 3000 行から約 150 行へ短くなった。 - また開発期間は Java 版の実装で、3 ヶ月程度かかったが、 Haskell 版の実装は 2 週間程度であった。 + Jungle は、様々なシステムに組み込むことができ、簡単なCMSとして掲示板システムを作成した。

- これにより、関数型プログラミングではコードは短くなり、生産性が向上することが分かった。 - -

-
- -
-

- 性能評価 -

-

- 非破壊的木構造データベース Jungle を用いて簡易掲示板システムを作成し、既存の Java 版との性能比較を行った。 + 掲示板システムを利用して、Haskell 版 Jungle と Java 版 Jungle の性能比較を行う。

- Haskell 版 Jungle の HTTP サーバには、Warp を用いた。 - Warpは、Haskell で書かれた軽量・高速な HTTP サーバである。 + 実験方法を以下に示す。

-
- -
-

- 実験方法 -

-

- 実験環境 -

+

実験環境

負荷をかける対象であるサーバは、マルチコア環境が生かされているか確認するためにコア数の多いマシンを用いる

@@ -378,9 +323,7 @@
-

- 実験結果 -

+

実験結果

@@ -390,92 +333,75 @@

- -　　 左が読み込み、右が書き込みの実験結果である。 + 縦軸は実行時間、横軸はノード数である。

- +

+ ノード数が増えると負荷が上昇するため、実行にかかる時間が伸びている。 +

Haskell 版および Java 版の Jungle は、ほぼ同程度の速度が出ていることが分かる。

-

- 並列実行 -

+

Haskell 版 Jungle の課題

- Haskell 版 Jungle では、並列実行に問題を抱えている。 - 複数のスレッドが立ち上がり、並列実行していることは確認したが、シングルコアで実行した場合と比較して実行結果が遅くなる。 + Haskell版 Jungle は、Java 版と同程度の速度が出ているが、まだ速度向上の余地がある。 +

+

+ 並列実行と、メモリ領域効率の改良が可能である。

-

- 並列実行 -

- +

並列実行

+

+ Haskell 版 Jungle では、並列実行に改良の余地がある。 + 現在、Haskell 版 Jungle はシングルコアで実行している。 +

+

- 本研究とは別に、簡単な例題を並列で動かした場合でも期待する実行速度の向上は得られなかった。 - - 並列処理で速度向上を達成することは今後の課題である。 + 並列実行を行った場合、複数のスレッドが立ち上がり、処理を行っていることは確認できた。 + しかしながら、シングルコアで実行した場合と比較して実行結果が遅くなる。 + マルチコアで実行した際の速度向上の達成のために、オーバーヘッドとなっている部分を見直し改善する必要がある。

- +
+ +
-

- 遅延評価 - -

+

メモリ領域の効率

+

+ Haskell 版 Jungle は、全ての評価を遅延評価で行っている。 + 書き込みの際、何かしらの結果を表示するまで、簡約可能な式の状態で積まれたままとなる。 +

- Haskell は遅延評価を行うが、書き込みの際に問題が生じる。 - - 何かしらの結果を表示するまで、簡約可能な式の状態で積まれたままとなる。 - その際メモリを消費し、効率のよい領域に入りきらないサイズになると実行結果が遅くなる。 + 適切な箇所で、即時評価を行うように変更することでメモリ領域の効率を改善できる。 +

+

+ メモリ領域の効率は、大量に書き込みだけを行った場合に問題となる。 + 大量に書き込みだけを行った場合、簡約可能な式が積まれ続ける。 + その際、効率のよい領域に入りきらないサイズになると実行結果が遅くなる。 + 現在は、推奨されるヒープ領域のサイズを変更している。

-
-

- 遅延評価 -

+
+

メモリ領域の効率

- 評価を行ったあとに実行時間がどのように変わるかを示すために、実験方法を変更した。 - - 以下に示す。 + ヒープ領域のサイズを変更しない場合の実験結果を示す。 + また、読み込みを行った際に、実行速度が改善することを示すために、クラスタ台数を10台増やすごとに一度読み込みを挟む。

-
    -
  • クラスタ台数を10台増やすごとに一度読み込みを挟む -
  • 推奨されるヒープ領域のサイズを変更しない -
-
- -
-

- 遅延評価 -

- +
+ +

書き込みを繰り返すと実行時間が悪化し、読み込み後、実行時間が下がる。 読み込みの際には、数万回以上の書き込みを処理するため数秒から数十秒かかる。 書き込みの順序は正しく処理されている。

-

- この問題を解決するために、全て遅延評価するのではなく、適切な箇所で即時評価を行うことで領域効率を改善する必要がある -

@@ -483,10 +409,9 @@ まとめ
    - -
  • Haskell による非破壊的木構造データベース Jungle を実装した -
  • 木構造データベース Jungle と、HTTP サーバ Warp を用いて、簡易掲示板システムを開発し、既存の Java の実装と同程度の性能を達成できた -
  • Haskell 版 Jungle は、Java の実装と比較して開発期間およびコード行数は短くなった。 +
  • Haskell による 非破壊的木構造データベース Jungle を実装した +
  • 実装した Haskell 版 Jungle は Java 版 Jungle と同程度の性能を達成できた +
  • Haskell 版 Jungle は、Java の実装と比較してコード行数および開発期間は短くなった
@@ -495,14 +420,10 @@ 今後の課題 - - -