Check-in [ec5ea2c8d2]

Many hyperlinks are disabled.
Use anonymous login to enable hyperlinks.

Overview
Comment:Add instrumentation of generated code for performance analysis.
Timelines: family | ancestors | descendants | both | trunk
Files: files | file ages | folders
SHA1:ec5ea2c8d29a052ca710d3d94333ef517d39977a
User & Date: kbk 2015-01-31 17:06:00
Context
2015-01-31
20:17
Added a peephole optimization where a join or antijoin immediately followed by a project gets coalesced into a single operation. Leaf check-in: 45268b8331 user: kbk tags: trunk
17:06
Add instrumentation of generated code for performance analysis. check-in: ec5ea2c8d2 user: kbk tags: trunk
2015-01-19
20:06
Add a 'tclMethod' method for introducing a new method on an existing database. check-in: c410a3e915 user: kbk tags: trunk
Changes

Changes to library/datalog.tcl.

1550
1551
1552
1553
1554
1555
1556



















1557
1558
1559
1560
1561
1562
1563
1564
1565
1566
1567
1568
1569
1570
1571
1572
1573





1574




1575
1576
1577
1578
1579
1580
1581
1582

1583
1584

1585
1586
1587
1588
1589
1590
1591
1592
1593
1594
1595
1596
1597

1598
1599

1600
1601

1602
1603

1604
1605

1606
1607

1608
1609
1610
1611
1612
1613
1614
....
1626
1627
1628
1629
1630
1631
1632

1633
1634

1635
1636

1637
1638

1639
1640

1641
1642

1643
1644

1645
1646

1647
1648

1649
1650

1651
1652
1653
1654
1655
1656
1657
....
1662
1663
1664
1665
1666
1667
1668



1669
1670
1671
1672
1673
1674
1675
....
1975
1976
1977
1978
1979
1980
1981
1982
1983
1984
1985






1986
1987
1988
1989
1990
1991
1992
....
2007
2008
2009
2010
2011
2012
2013









2014
2015
2016
2017
2018
2019
2020
2021
2022
2023
2024
2025
2026
2027
2028

	}

	# Union the result into the destination
	lappend intcode [list UNION $predicate $predicate $joinSource]
	
    }




















    # Method: generateCode
    #
    #	Generates Tcl code for a Datalog program from the intermediate code 
    #	lists

    method generateCode {args} {

	set loaders {}

	set prologue \n
	set body \n
	set epilogue \n

	set ind0 {    }
	set ind {    }






	foreach instr $intcode {




	    switch -exact -- [lindex $instr 0] {
		RELATION {
		    $db relation [lindex $instr 1] {*}[lindex $instr 2]
		    append prologue $ind0 [$db set [lindex $instr 1] {}] \n
		    append epilogue $ind0 [$db set [lindex $instr 1] {}] \n
		}
		
		ANTIJOIN {

		    append body $ind \
			[$db antijoin {*}[lrange $instr 1 end]] \n

		}
		BEGINLOOP {
		    append body $ind "while 1 \{\n"
		    set ind "$ind    "
		}
		ENDLOOP {
		    set command [$db === [lindex $instr 1] [lindex $instr 2]]
		    append body \
			$ind if { } \{ \[ $command \] \} { } break \n
		    set ind [string replace $ind end-3 end]
		    append body $ind "\}" \n
		}
		EQUALITY {

		    append body $ind \
			[$db equate {*}[lrange $instr 1 end]] \n

		}
		INEQUALITY {

		    append body $ind \
			[$db inequality {*}[lrange $instr 1 end]] \n

		}
		JOIN {

		    append body $ind \
			[$db join {*}[lrange $instr 1 end]] \n

		}
		LOAD {
		    # append body $ind # $instr \n
		    set relation [lindex $instr 1]
		    if {![dict exists $loaders $relation]} {
			dict set loaders $relation [$db loader $relation]
		    }
................................................................................
				error "in generateCode: can't happen"
			    }
			}
		    }
		    append body \n
		}
		NEGATE {

		    append body $ind \
			[$db negate {*}[lrange $instr 1 end]] \n

		}
		PROJECT {

		    append body $ind \
			[$db project {*}[lrange $instr 1 end]] \n

		}
		RENAME {

		    append body $ind \
			[$db replace {*}[lrange $instr 1 end]] \n

		}
		SET {

		    append body $ind \
			[$db set {*}[lrange $instr 1 end]] \n

		}
		UNION {

		    append body $ind \
			[$db union {*}[lrange $instr 1 end]] \n

		}

		RESULT {
		    if {[llength $args] != 2} {
			error "wrong # args"; # TODO - better reporting
		    }
		    append body \
................................................................................

		default {
		    error "in generateCode: can't happen"
		}
	    }

	}



	return $prologue$body$epilogue

    }

    # Method: getRule
    #
    #	Looks up a rule
................................................................................
# }
#
# # Populate the 'grandparent' relation
# listGrandparents
# # What items are the grandparents of item 0?
# puts [grandparents 0]; # prints a list containing 3, 4, 5, and 6

proc bdd::datalog::compileProgram {db prelude programText args} {

    variable parser







    switch -exact -- [llength $args] {
	1 {
	    lassign $args postlude
	    set dictAndAction {}
	}
	3 {
	    lassign $args dict action postlude
................................................................................
	lassign [lex $programText] tokens values
	
	# Parse the program and feed the parse into $program
	$parser parse $tokens $values $program

	# Plan the execution
	set plan [$program planExecution]










	# Translate the execution plan to relational algebra
	$program translateExecutionPlan $plan

	# Generate code
	append result \
	    $prelude \n \
	    [$program generateCode {*}$dictAndAction] \n \
	    $postlude

    } finally {

	$program destroy

    }







>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>






|










>
>
>
>
>

>
>
>
>








>


>













>


>


>


>


>


>







 







>


>


>


>


>


>


>


>


>


>







 







>
>
>







 







|



>
>
>
>
>
>







 







>
>
>
>
>
>
>
>
>







|







1550
1551
1552
1553
1554
1555
1556
1557
1558
1559
1560
1561
1562
1563
1564
1565
1566
1567
1568
1569
1570
1571
1572
1573
1574
1575
1576
1577
1578
1579
1580
1581
1582
1583
1584
1585
1586
1587
1588
1589
1590
1591
1592
1593
1594
1595
1596
1597
1598
1599
1600
1601
1602
1603
1604
1605
1606
1607
1608
1609
1610
1611
1612
1613
1614
1615
1616
1617
1618
1619
1620
1621
1622
1623
1624
1625
1626
1627
1628
1629
1630
1631
1632
1633
1634
1635
1636
1637
1638
1639
1640
1641
1642
1643
1644
1645
1646
1647
1648
1649
1650
....
1662
1663
1664
1665
1666
1667
1668
1669
1670
1671
1672
1673
1674
1675
1676
1677
1678
1679
1680
1681
1682
1683
1684
1685
1686
1687
1688
1689
1690
1691
1692
1693
1694
1695
1696
1697
1698
1699
1700
1701
1702
1703
....
1708
1709
1710
1711
1712
1713
1714
1715
1716
1717
1718
1719
1720
1721
1722
1723
1724
....
2024
2025
2026
2027
2028
2029
2030
2031
2032
2033
2034
2035
2036
2037
2038
2039
2040
2041
2042
2043
2044
2045
2046
2047
....
2062
2063
2064
2065
2066
2067
2068
2069
2070
2071
2072
2073
2074
2075
2076
2077
2078
2079
2080
2081
2082
2083
2084
2085
2086
2087
2088
2089
2090
2091
2092

	}

	# Union the result into the destination
	lappend intcode [list UNION $predicate $predicate $joinSource]
	
    }

    method startMeasure {ind bodyVar instrumentLevel} {
	if {$instrumentLevel >= 1} {
	    upvar 1 $bodyVar body
	    append body $ind {set tock [clock microseconds]} \n
	}
    }
    method endMeasure {ind bodyVar instrumentLevel instr} {
	if {$instrumentLevel >= 1} {
	    upvar 1 $bodyVar body
	    append body $ind {set beadCount 0} \n
	    append body $ind {foreach {col bit n} [sys profile } [lindex $instr 1] {] } \{ \n
	    append body $ind {    incr beadCount $n} \n
	    append body $ind \} \n
	    append body $ind \
		[string map [list @instr $instr] \
		     {puts [format "%10.6f: %6i @instr" [expr {1.0e-6*([clock microseconds] - $tock)}] $beadCount]}] \n
	}
    }

    # Method: generateCode
    #
    #	Generates Tcl code for a Datalog program from the intermediate code 
    #	lists

    method generateCode {instrumentLevel args} {

	set loaders {}

	set prologue \n
	set body \n
	set epilogue \n

	set ind0 {    }
	set ind {    }

	set pc 0
	if {$instrumentLevel >= 1} {
	    puts "Relational algebra for Datalog program:"
	    set pc 0
	}
	foreach instr $intcode {
	    if {$instrumentLevel >= 1} {
		puts [format {%6d: %s} $pc $instr]
		incr pc
	    }
	    switch -exact -- [lindex $instr 0] {
		RELATION {
		    $db relation [lindex $instr 1] {*}[lindex $instr 2]
		    append prologue $ind0 [$db set [lindex $instr 1] {}] \n
		    append epilogue $ind0 [$db set [lindex $instr 1] {}] \n
		}
		
		ANTIJOIN {
		    my startMeasure $ind body $instrumentLevel
		    append body $ind \
			[$db antijoin {*}[lrange $instr 1 end]] \n
		    my endMeasure $ind body $instrumentLevel $instr
		}
		BEGINLOOP {
		    append body $ind "while 1 \{\n"
		    set ind "$ind    "
		}
		ENDLOOP {
		    set command [$db === [lindex $instr 1] [lindex $instr 2]]
		    append body \
			$ind if { } \{ \[ $command \] \} { } break \n
		    set ind [string replace $ind end-3 end]
		    append body $ind "\}" \n
		}
		EQUALITY {
		    my startMeasure $ind body $instrumentLevel
		    append body $ind \
			[$db equate {*}[lrange $instr 1 end]] \n
		    my endMeasure $ind body $instrumentLevel $instr
		}
		INEQUALITY {
		    my startMeasure $ind body $instrumentLevel
		    append body $ind \
			[$db inequality {*}[lrange $instr 1 end]] \n
		    my endMeasure $ind body $instrumentLevel $instr
		}
		JOIN {
		    my startMeasure $ind body $instrumentLevel
		    append body $ind \
			[$db join {*}[lrange $instr 1 end]] \n
		    my endMeasure $ind body $instrumentLevel $instr
		}
		LOAD {
		    # append body $ind # $instr \n
		    set relation [lindex $instr 1]
		    if {![dict exists $loaders $relation]} {
			dict set loaders $relation [$db loader $relation]
		    }
................................................................................
				error "in generateCode: can't happen"
			    }
			}
		    }
		    append body \n
		}
		NEGATE {
		    my startMeasure $ind body $instrumentLevel
		    append body $ind \
			[$db negate {*}[lrange $instr 1 end]] \n
		    my endMeasure $ind body $instrumentLevel $instr
		}
		PROJECT {
		    my startMeasure $ind body $instrumentLevel
		    append body $ind \
			[$db project {*}[lrange $instr 1 end]] \n
		    my endMeasure $ind body $instrumentLevel $instr
		}
		RENAME {
		    my startMeasure $ind body $instrumentLevel
		    append body $ind \
			[$db replace {*}[lrange $instr 1 end]] \n
		    my endMeasure $ind body $instrumentLevel $instr
		}
		SET {
		    my startMeasure $ind body $instrumentLevel
		    append body $ind \
			[$db set {*}[lrange $instr 1 end]] \n
		    my endMeasure $ind body $instrumentLevel $instr
		}
		UNION {
		    my startMeasure $ind body $instrumentLevel
		    append body $ind \
			[$db union {*}[lrange $instr 1 end]] \n
		    my endMeasure $ind body $instrumentLevel $instr
		}

		RESULT {
		    if {[llength $args] != 2} {
			error "wrong # args"; # TODO - better reporting
		    }
		    append body \
................................................................................

		default {
		    error "in generateCode: can't happen"
		}
	    }

	}
	if {$instrumentLevel > 0} {
	    append prologue $ind "puts \"\[info level 0\]:\""
	}
	return $prologue$body$epilogue

    }

    # Method: getRule
    #
    #	Looks up a rule
................................................................................
# }
#
# # Populate the 'grandparent' relation
# listGrandparents
# # What items are the grandparents of item 0?
# puts [grandparents 0]; # prints a list containing 3, 4, 5, and 6

proc bdd::datalog::compileProgram {db args} {

    variable parser

    set instrumentLevel 0
    if {[lindex $args 0] eq {-instrument}} {
	set args [lassign $args - instrumentLevel]
    }
    set args [lassign $args prelude programText]

    switch -exact -- [llength $args] {
	1 {
	    lassign $args postlude
	    set dictAndAction {}
	}
	3 {
	    lassign $args dict action postlude
................................................................................
	lassign [lex $programText] tokens values
	
	# Parse the program and feed the parse into $program
	$parser parse $tokens $values $program

	# Plan the execution
	set plan [$program planExecution]

	if {$instrumentLevel >= 1} {
	    puts "Execution plan for Datalog program:"
	    set p 0
	    foreach instr $plan {
		puts [format {%6d: %s} $p $instr]
		incr p
	    }
	}

	# Translate the execution plan to relational algebra
	$program translateExecutionPlan $plan

	# Generate code
	append result \
	    $prelude \n \
	    [$program generateCode $instrumentLevel {*}$dictAndAction] \n \
	    $postlude

    } finally {

	$program destroy

    }