Functor Domain Layout - Revision history

Thomas Linder Puls: category

2016-03-04T09:46:22Z

Thomas Linder Puls: size of

2015-01-21T20:36:30Z

size of

← Older revision		Revision as of 22:36, 21 January 2015
Line 5:		Line 5:
	Functor domains with (just) one alternative (here called a struct) is laid out in a compact way. The layout is fully compatible with Microsoft C/C++'s struct layout.		Functor domains with (just) one alternative (here called a struct) is laid out in a compact way. The layout is fully compatible with Microsoft C/C++'s struct layout.

	All data have an "alignment" size:		All data have an '''alignment''' size:
	* For simple data (numbers, etc) it is the size of the data.		* For simple data (numbers, etc) it is the size of the data.
	* For pointers it is the size of a pointer.		* For pointers it is the size of a pointer.
Line 16:		Line 16:
	* <vp>real</vp> -> 8 bytes		* <vp>real</vp> -> 8 bytes
	* <vp>string</vp> -> 4 bytes in a 32bit program; 8 bytes in a 64bit program		* <vp>string</vp> -> 4 bytes in a 32bit program; 8 bytes in a 64bit program
	* <vp>fff(integer8 A, unsigned16 B, real C)</vp> -> 8 bytes because <vp>real</vp> have alignment 8 bytes		* <vp>fff(integer8 A, unsigned16 B, real C)</vp> -> 8 bytes because <vp>real</vp> have alignment 8 bytes}}
	}}

	When laying out a struct term all components are placed at the next available byte that match their alignment.		When laying out a struct term all components are placed at the next available byte that match their alignment.
Line 41:		Line 40:
	<tr><td>14</td><td>C (byte 7)</td></tr>		<tr><td>14</td><td>C (byte 7)</td></tr>
	<tr><td>15</td><td>C (byte 8)</td></tr>		<tr><td>15</td><td>C (byte 8)</td></tr>
	</table>		</table>}}
	}}

	Besides being compatible with C/C++/Windows API the purpose of the alignment is to ensure that memory operations are performed efficient: When fetching unaligned data the processor will have to do it as two separate memory fetches and perform internal rearrangement of the data before it gets the right shape).		Besides being compatible with C/C++/Windows API the purpose of the alignment is to ensure that memory operations are performed efficient: When fetching unaligned data the processor will have to do it as two separate memory fetches and perform internal rearrangement of the data before it gets the right shape).

	The built-in predicate [[Language Reference/Built-in entities#sizeOf\|sizeOf]] and [[Language Reference/Built-in entities#sizeOfDomain\|sizeOfDomain]] predicates returns the ~~total~~ size of the ~~struct i~~.e. 16 ~~(bytes)~~ for the <vp>fff</vp> ~~struct in the example~~.		=== sizeOf & sizeOfDomain ===

			The built-in predicate [[Language Reference/Built-in entities#sizeOf\|sizeOf]] and [[Language Reference/Built-in entities#sizeOfDomain\|sizeOfDomain]] predicates returns the size of the allocated piece of memory. I.e. 16 for the <vp>fff</vp> term above.

	== Multiple alternatives ==		== Multiple alternatives ==
Line 69:		Line 69:
	<vip>domains		<vip>domains
	boolean = false; true.</vip>		boolean = false; true.</vip>
	Both <vp>false</vp> and <vp>true</vp> are functors alternative that doesn't carry any data. <vp>false</vp> will be represented as <vp>0</vp> and <vp>true</vp> as <vp>1</vp>.		Both <vp>false</vp> and <vp>true</vp> are functors alternative that doesn't carry any data. <vp>false</vp> will be represented as <vp>0</vp> and <vp>true</vp> as <vp>1</vp>.}}
	}}

	=== Alternatives with data ===		=== Alternatives with data ===
Line 83:		Line 82:

	Many domains have less than 8 data carrying alternatives, so the "default" representation is not used very often.		Many domains have less than 8 data carrying alternatives, so the "default" representation is not used very often.

	~~In a 32 bit program there are only unused 2 bits giving 4 values. And thus 3 or 4 functor free alternatives.~~

	{{Example\|		{{Example\|
Line 95:		Line 92:
	* The first 7 alternatives (<vp>functorFree1</vp> - <vp>functorFree7</vp>) will be represented as a pointer + a functor number (0-6), where the pointer points to the allocated data (which does not contain a functor).		* The first 7 alternatives (<vp>functorFree1</vp> - <vp>functorFree7</vp>) will be represented as a pointer + a functor number (0-6), where the pointer points to the allocated data (which does not contain a functor).
	* The remaining alternatives (<vp>dataCarry1</vp>, <vp>dataCarry2</vp>, ...) )will be represented as pointer+7, where the pointer points to the allocated data (which does contain a functor)}}		* The remaining alternatives (<vp>dataCarry1</vp>, <vp>dataCarry2</vp>, ...) )will be represented as pointer+7, where the pointer points to the allocated data (which does contain a functor)}}

			=== 32 bit programs ===

			In a 32 bit program there are only unused 2 bits giving 4 values. And thus 3 or 4 functor free alternatives.

			=== sizeOf & sizeOfDomain ===

			The built-in predicate [[Language Reference/Built-in entities#sizeOf\|sizeOf]] will return the size of a pointer for a data-free alternative, for data carrying alternatives it will return the size of the allocated memory.

			The built-in predicate [[Language Reference/Built-in entities#sizeOfDomain\|sizeOfDomain]] does not have access to a specific term, so it returns the size of largest alternative.

	[[Category:Tutorials]]		[[Category:Tutorials]]
	[[Category:Memory Handling]]		[[Category:Memory Handling]]

Thomas Linder Puls: /* References */ remove header

2015-01-21T16:42:34Z

References: remove header

← Older revision		Revision as of 18:42, 21 January 2015
Line 95:		Line 95:
	* The first 7 alternatives (<vp>functorFree1</vp> - <vp>functorFree7</vp>) will be represented as a pointer + a functor number (0-6), where the pointer points to the allocated data (which does not contain a functor).		* The first 7 alternatives (<vp>functorFree1</vp> - <vp>functorFree7</vp>) will be represented as a pointer + a functor number (0-6), where the pointer points to the allocated data (which does not contain a functor).
	* The remaining alternatives (<vp>dataCarry1</vp>, <vp>dataCarry2</vp>, ...) )will be represented as pointer+7, where the pointer points to the allocated data (which does contain a functor)}}		* The remaining alternatives (<vp>dataCarry1</vp>, <vp>dataCarry2</vp>, ...) )will be represented as pointer+7, where the pointer points to the allocated data (which does contain a functor)}}

	~~==References==~~

	[[Category:Tutorials]]		[[Category:Tutorials]]
	[[Category:Memory Handling]]		[[Category:Memory Handling]]

Thomas Linder Puls: init

2015-01-21T16:41:45Z

init

New page

The tutorial describes the memory layout of functor domain in Visual Prolog. A functor term is allocated in the (memory) heap, and predicates etc works with a pointer to the allocated memory.

== One alternative ==

Functor domains with (just) one alternative (here called a struct) is laid out in a compact way. The layout is fully compatible with Microsoft C/C++'s struct layout.

All data have an "alignment" size:
* For simple data (numbers, etc) it is the size of the data.
* For pointers it is the size of a pointer.
* For a struct it is the largest of the components alignment sizes (unless an explicit alignment is stated).

{{Example|
* <vp>unsigned8</vp> -> 1 byte
* <vp>integer</vp> -> 4 bytes
* <vp>real</vp> -> 8 bytes
* <vp>string</vp> -> 4 bytes in a 32bit program; 8 bytes in a 64bit program
* <vp>fff(integer8 A, unsigned16 B, real C)</vp> -> 8 bytes because <vp>real</vp> have alignment 8 bytes
}}

When laying out a struct term all components are placed at the next available byte that match their alignment.

{{Example| So <vp>fff(integer8 A, unsigned16 B, real C)</vp> is laid out as follows:

<table {{prettytable|style=text-align: center;}}>
<tr><th>Offset</th><th>Contents</th></tr>
<tr><td>0</td><td>A</td></tr>
<tr><td>1</td><td>(empty)</td></tr>
<tr><td>2</td><td>B (low)</td></tr>
<tr><td>3</td><td>B (high)</td></tr>
<tr><td>4</td><td>(empty)</td></tr>
<tr><td>5</td><td>(empty)</td></tr>
<tr><td>6</td><td>(empty)</td></tr>
<tr><td>7</td><td>(empty)</td></tr>
<tr><td>8</td><td>C (byte 1)</td></tr>
<tr><td>9</td><td>C (byte 2)</td></tr>
<tr><td>10</td><td>C (byte 3)</td></tr>
<tr><td>11</td><td>C (byte 4)</td></tr>
<tr><td>12</td><td>C (byte 5)</td></tr>
<tr><td>13</td><td>C (byte 6)</td></tr>
<tr><td>14</td><td>C (byte 7)</td></tr>
<tr><td>15</td><td>C (byte 8)</td></tr>
</table>
}}

Besides being compatible with C/C++/Windows API the purpose of the alignment is to ensure that memory operations are performed efficient: When fetching unaligned data the processor will have to do it as two separate memory fetches and perform internal rearrangement of the data before it gets the right shape).

The built-in predicate [[Language Reference/Built-in entities#sizeOf|sizeOf]] and [[Language Reference/Built-in entities#sizeOfDomain|sizeOfDomain]] predicates returns the total size of the struct i.e. 16 (bytes) for the <vp>fff</vp> struct in the example.

== Multiple alternatives ==

If there are more alternatives in the functor domain the layout is much less compact, because in that case each field is laid out in a "pointer" size piece of memory. Future releases of Visual Prolog will (almost definitely) adopt the compact layout for such domains as well.

When there are several alternatives it is necessary to distinguish between the different alternatives. The default mechanism for this is to place an extra integer first in the struct representing the functor. Visual Prolog (version 7.5) do however avoid this extra field in two ways.

=== Alternatives without data ===

On the Windows platform a pointer (pointing to the heap) will never be a small number. Visual Prolog exploit this property for the representation of functor alternatives that doesn't carry any data. Instead of allocating any data at all and pointing to it, the functor will be represented directly in as a small pointer value.

{{Example|
<vip>domains
tree = empty; node(tree Left, integer Value, tree Right).</vip>
<vp>empty</vp> is a functor alternative that doesn't carry any data. So its representation will be a small pointer value (= 0). <vp>node</vp> on the other hand do carry data so its representation will be a pointer to the memory representing the node.
}}

If a domain only contains functor alternatives that doesn't carry data, it effectively becomes an enumeration domain where numbers represents the different enumerants.

{{Example|
<vip>domains
boolean = false; true.</vip>
Both <vp>false</vp> and <vp>true</vp> are functors alternative that doesn't carry any data. <vp>false</vp> will be represented as <vp>0</vp> and <vp>true</vp> as <vp>1</vp>.
}}

=== Alternatives with data ===

If an alternative carries data it will be represented as a pointer to the memory that carries the data. The memory is always allocated on a pointer size boundary, here we will only consider 64 bit programs so alignment is on 8 byte boundaries (the reader will have to "translate" to 32 bit if necessary). The 3 least significant bits of a pointer that points to an 8 byte boundary will be zero, so they are in a sense unused. Visual Prolog exploit these 3 unused bits in the following way. 3 bits gives 8 values. 7 of these are used to represent a functor value the last value means the "remaning" cases.

So for the first 7 functor alternatives that carry data, the allocated data will not contain a functor value, instead the functor number is encoded in the three least significant bits of the pointer to the data. (This encoding can be treated rather efficiently, but the details is outside the scope of this article).

* If there are no more alternatives (after the data-less ones and up to 7 data carrying ones) we are done.
* If there is exactly one more alternative this doesn't need a functor and it treated in the same way as the 7 first ones.
* If there are more than one alternative left these alternatives will be represented in the "default" way with a functor-number as the first piece of data in the allocated memory.

Many domains have less than 8 data carrying alternatives, so the "default" representation is not used very often.

In a 32 bit program there are only unused 2 bits giving 4 values. And thus 3 or 4 functor free alternatives.

{{Example|
<vip>domains
example = enum1; enum2, enum3; ...
functorFree1(...); functorFree2(...); functorFree3(...); functorFree4(...);
functorFree5(...); functorFree6(...); functorFree7(...);
dataCarry1(...); dataCarry2(...); ...</vip>
* The data free functors <vp>enum1</vp>, <vp>enum2</vp>, <vp>enum3</vp>, ... are represented as small numbers <vp>0</vp>, <vp>1</vp>, <vp>2</vp>, ...
* The first 7 alternatives (<vp>functorFree1</vp> - <vp>functorFree7</vp>) will be represented as a pointer + a functor number (0-6), where the pointer points to the allocated data (which does not contain a functor).
* The remaining alternatives (<vp>dataCarry1</vp>, <vp>dataCarry2</vp>, ...) )will be represented as pointer+7, where the pointer points to the allocated data (which does contain a functor)}}

==References==

[[Category:Tutorials]]
[[Category:Memory Handling]]

← Older revision		Revision as of 11:46, 4 March 2016
Line 103:		Line 103:
	The built-in predicate [[Language Reference/Built-in entities#sizeOfDomain\|sizeOfDomain]] does not have access to a specific term, so it returns the size of largest alternative.		The built-in predicate [[Language Reference/Built-in entities#sizeOfDomain\|sizeOfDomain]] does not have access to a specific term, so it returns the size of largest alternative.

	~~[[Category:Tutorials]]~~
	[[Category:Memory Handling]]		[[Category:Memory Handling]]