Im­prove this page Quickly fork, edit on­line, and sub­mit a pull re­quest for this page. Re­quires a signed-in GitHub ac­count. This works well for small changes. If you'd like to make larger changes you may want to con­sider using local clone. Page wiki View or edit the com­mu­nity-main­tained wiki page as­so­ci­ated with this page.

D Slices

by Steven Schveighof­fer

One of the most pleas­ant fea­tures of the D lan­guage is its im­ple­men­ta­tion of slices. Every time I use a pro­gram­ming lan­guage that isn't D, I find my­self lament­ing for D's slice syn­tax. Not only is it con­cise and ef­fi­cient, but things "just work" when you are deal­ing with slices.

I'll go over some of the back­ground and in­ter­nals of D slices and ar­rays, and hope­fully after read­ing this, you will have a clearer un­der­stand­ing of the proper ways to use D slices, as well as an idea of how fun­da­men­tally dif­fer­ent they are than nor­mal ar­rays!

An Over­flow­ing Prob­lem

In most lan­guages, an array is a built-in type which man­ages its own data, and is passed around by ref­er­ence. One refers to the en­tire thing as an "Array", and as­so­ci­ates all the op­er­a­tions for the array (such as set­ting val­ues, ap­pend­ing data for dy­namic ar­rays, ob­tain­ing the length) to that type.

How­ever, D takes its lin­eage from C, where an array is sim­ply a chunk of con­tigu­ous data. In C, a ref­er­ence to an array or array seg­ment is as sim­ple as a pointer (an ex­plicit ref­er­ence). C's ar­rays are dis­tinctly un­man­aged by the type that refers to them -- the pointer. The only op­er­a­tions sup­ported are to re­trieve and set data using an off­set from the pointer.

For those of you un­fa­mil­iar with C, here are some ex­am­ples of array usage in C (these also work in D):

arr[0] = 4; /* sets the first element of the array 'arr' to 4 */
x = arr[1]; /* retrieves the second element of the array 'arr' into x */

Every­thing else (length, ap­pend­ing, al­lo­ca­tion, de­struc­tion) is left up to li­brary func­tions and as­sump­tion/doc­u­men­ta­tion. So what is so wrong with this con­cept? One of the largest prob­lems with C ar­rays is the abil­ity to ac­cess any data via the pointer, even data that doesn't be­long to the array. You can even use neg­a­tive in­dexes! Not to men­tion that the array uses the exact same type as a pointer to a sin­gle item. When you get a pointer as a pa­ra­me­ter to a func­tion, that could be an array, or it could be just a pointer to a sin­gle item. Cue buffer over­flow at­tacks. You can read more about this in Wal­ter Bright's ar­ti­cle, "C's biggest mis­take"

In­tro­duc­ing Slices

So how does D im­prove things? In many ways, D's ar­rays are sim­i­lar to C's ar­rays. In fact, D sup­ports C's array syn­tax using point­ers. How­ever, D pro­vides a new type that builds on C array syn­tax called a slice. A slice is a seg­ment of an array (dy­namic or oth­er­wise) that tracks both the pointer and the length of the seg­ment. With the com­bined pro­tec­tion of hav­ing the length of the data, and the garbage col­lec­tor to man­age the mem­ory back­ing the data, slices are an ex­tremely pow­er­ful, dy­namic con­cept that is safe from most mem­ory cor­rup­tion is­sues. In ad­di­tion, D slices sup­port ex­tend­ing with sim­ple func­tions which take a slice as the first pa­ra­me­ter. This al­lows one to add any func­tion­al­ity you want to a built-in type via prop­er­ties or meth­ods. With D slices, one can write high-per­for­mance code with el­e­gant and con­cise syn­tax that is awk­ward or in­ef­fi­cient in al­most any other lan­guage.

Let's see some D slices in ac­tion:

import std.stdio;

void main()
{
    int[] a;             // a is a slice

    a = new int[5];      // allocate a dynamic array of integers that has at least 5
                         // elements, and give me a slice to the first 5.  Note
                         // that all data in D is default assigned, int's are
                         // defaulted to 0, so this array contains five 0's

    int[] b = a[0..2];   // This is a 'slicing' operation.  b now refers to the
                         // first two elements of a.  Note that D uses open interval
                         // for the upper limit, so a[2] is not included in b.

    int[] c = a[$-2..$]; // c refers to the last two elements of a
                         // ($ stands for length inside a slice or index operation).

    c[0] = 4;            // this also assigns a[3]
    c[1] = 5;            // this also assigns a[4]

    b[] = c[];           // assign the first two elements of a[] to the value from
                         // the last two elements (4, 5).

    writeln(a);          // prints "[4, 5, 0, 4, 5]"

    int[5] d;            // d is a fixed sized array, allocated on the stack
    b = d[0..2];         // slices can point at fixed sized arrays too!
}

You may no­tice some­thing puz­zling about the de­scrip­tion of the al­lo­ca­tion of the array: "al­lo­cate a dy­namic array of in­te­gers that has at least 5 el­e­ments, and give me a slice to the first 5." Why isn't it just "al­lo­cate a dy­namic array of 5 el­e­ments"? Even ex­pe­ri­enced D coders have trou­ble with D's array con­cepts some­times, and for quite good rea­son. D's slices are not proper dy­namic array types (at least not under the hood) even though they ap­pear to be. What they do is pro­vide a safe and easy in­ter­face to ar­rays of any type (dy­namic or oth­er­wise). So let's dis­cuss prob­a­bly the most com­mon mis­con­cep­tion of D slices.

Who's Re­spon­si­ble?

A slice in D seems like a dy­namic array in al­most all as­pects of the con­cept -- when passed with­out adorn­ments, the data re­ferred to is passed by ref­er­ence, and it sup­ports all the prop­er­ties and func­tions one would ex­pect a dy­namic array type to sup­port. But there is one very im­por­tant dif­fer­ence. A slice does not own the array, it ref­er­ences the array. That is, the slice is not re­spon­si­ble for al­lo­ca­tion or deal­lo­ca­tion of its data. The re­spon­si­ble party for man­ag­ing a dy­namic array's mem­ory is the D run­time.

So where is the true dy­namic array type in D? It's hid­den by the run­time, and in fact, has no for­mal type. Slices are good enough, and as it turns out, the run­time is smart enough about what you want to do with the data, that you al­most never no­tice dy­namic ar­rays are miss­ing as a full-fledged type. In fact, most D coders con­sider the D slice to be the dy­namic array type -- it's even listed as a dy­namic array type in the spec! The lack of own­er­ship is very sub­tle and easy to miss.

An­other con­se­quence of this is that the length is not an array prop­erty, it's a slice prop­erty. This means the length field is not nec­es­sar­ily the length of the array, it's the length of the slice. This can be con­fus­ing to new­com­ers to the lan­guage. For in­stance, this code has a large flaw in it:

import std.stdio;

void shrinkTo2(int[] arr)
{
    if(arr.length > 2)
        arr.length = 2;
}

void main()
{
   int[] arr = new int[5];
   arr.shrinkTo2();     // note the ability to call shrinkTo2 as a method
   writeln(arr.length); // outputs 5
}

This might look like you changed the passed arr's length to 2, but it ac­tu­ally did not af­fect any­thing (as is proven by the out­put from writeln). This is be­cause even though the data is passed by ref­er­ence, the ac­tual pointer and length are passed by value. Many lan­guages have an array type whose prop­er­ties are all passed by ref­er­ence. No­tably, C# and Java ar­rays are ac­tu­ally fully ref­er­enced Ob­jects. C++'s vec­tor ei­ther passes both its data and prop­er­ties by ref­er­ence or by value.

To fix this prob­lem, you can do one of two things. Ei­ther you ex­plic­itly pass the slice by ref­er­ence via the ref key­word, or you re­turn the re­sult­ing slice to be re­as­signed. For ex­am­ple, here is how the sig­na­ture would look if the slice is passed by ref­er­ence:

void shrinkTo2(ref int[] arr)

Let's say you make this change, what hap­pens to the data be­yond the sec­ond el­e­ment? In D, since slices don't own the data, it's still there, man­aged by the neb­u­lous dy­namic array type. The rea­son is fun­da­men­tal: some other slice may still be ref­er­enc­ing that data! The fact that no sin­gle slice is the true owner of the data means no sin­gle slice can make any as­sump­tions about what else ref­er­ences the array data.

What hap­pens when no slices ref­er­ence that data? Enter D's garbage col­lec­tor. The garbage col­lec­tor is re­spon­si­ble for clean­ing up dy­namic ar­rays that no longer are ref­er­enced by any slices. In fact, it is the garbage col­lec­tor that makes much of D's slice usage pos­si­ble. You can slice and serve up seg­ments of dy­namic ar­rays, and never have to worry that you are leak­ing mem­ory, clob­ber­ing other slices, or worry about man­ag­ing the life­time of the array.

A Slice You Can Ap­pend On

D's slices sup­port ap­pend­ing more data to the end of the slice, much like a true dy­namic array type. The lan­guage has a spe­cific op­er­a­tor used for con­cate­na­tion and ap­pend­ing, the tilde (~). Here are some op­er­a­tions that ap­pend and con­cate­nate ar­rays:

int[] a;     // an empty slice references no data, but still can be appended to
a ~= 1;      // append some integers, this automatically allocates a new
a ~= 2;      // array to hold the elements.

a ~= [3, 4]; // append another array (this time, an array literal)
a = a ~ a;   // concatenate a with itself, a is now [1, 2, 3, 4, 1, 2, 3, 4]

int[5] b;    // a fixed-size array on the stack
a = b[1..$]; // a is a slice of b
a ~= 5;      // since a was pointing to stack data, appending always reallocates,
             // but works!

Any­one who cares about per­for­mance will won­der what hap­pens when you ap­pend the four el­e­ments. The slice does not own its data, so how does one avoid re­al­lo­cat­ing a new array on each ap­pend op­er­a­tion? One of the main re­quire­ments of D slices are that they are ef­fi­cient. Oth­er­wise, coders would not use them. D has solved this prob­lem in a way that is vir­tu­ally trans­par­ent to the pro­gram­mer, and this is one of the rea­sons slices seem more like true dy­namic ar­rays.

How it Works

Re­mem­ber be­fore when we al­lo­cated a new array, I said al­lo­cate a dy­namic array of at least n el­e­ments and give me a slice? Here is where the run­time earns its keep. The al­lo­ca­tor only al­lo­cates blocks in pow­ers of 2 up to a page of data (in 32-bit x86, a page of data is 4096 bytes), or in mul­ti­ples of pages. So when you al­lo­cate an array, you can eas­ily get a block that's larger than re­quested. For in­stance, al­lo­cat­ing a block of five 32 bit in­te­gers (which con­sumes 20 bytes) pro­vides you a block of 32 bytes. This leaves space for 3 more in­te­gers.

It's clearly pos­si­ble to ap­pend more in­te­gers into the array with­out re­al­lo­cat­ing, but the trick is to pre­vent "stomp­ing" on data that is valid and in use. Re­mem­ber, the slice doesn't know what other slices refer to that data, or re­ally where it is in the array (it could be a seg­ment at the be­gin­ning or the mid­dle). To make the whole thing work, the run­time stores the num­ber of used bytes in­side the block it­self (a minor draw­back is that the us­able space in the block is not as big as it could be. In our ex­am­ple, for in­stance, we can truly only store 7 in­te­gers be­fore need­ing to re­al­lo­cate into an­other block).

When we re­quest the run­time to ap­pend to a slice, it first checks to see that both the block is ap­pend­able (which means the used field is valid), and the slice ends at the same point valid data ends (it is not im­por­tant where the slice be­gins). The run­time then checks to see if the new data will fit into the un­used block space. If all of these checks pass, the data is writ­ten into the array block, and the stored used field is up­dated to in­clude the new data. If any of these checks fail, a new array block is al­lo­cated that will hold the ex­ist­ing and new data, which is then pop­u­lated with all the data. What hap­pens to the old block? If there were other slices ref­er­enc­ing it, it stays in place with­out being changed. If noth­ing else is ref­er­enc­ing it, it be­comes garbage and is re­claimed on the next col­lec­tion cycle. This al­lows you to safely re­al­lo­cate one slice with­out in­val­i­dat­ing any oth­ers. This is a huge de­par­ture from C/C++, where re­al­lo­cat­ing an array, or ap­pend­ing to a vec­tor can in­val­i­date other ref­er­ences to that data (point­ers or it­er­a­tors).

The re­sult is an ap­pend op­er­a­tion which is not only ef­fi­cient, but uni­ver­sally handy. When­ever you want to ap­pend a slice, you can, with­out worry about per­for­mance or cor­rup­tion is­sues. You don't even have to worry about whether a slice's data is heap al­lo­cated, stack al­lo­cated, in ROM, or even if it's null. The ap­pend op­er­a­tion al­ways suc­ceeds (given you have enough mem­ory), and the run­time takes care of all the dirty work in the back­ground.

De­ter­min­ism

There is one caveat with slice ap­pend­ing that can bite in­ex­pe­ri­enced, and even ex­pe­ri­enced D coders: the ap­par­ent non-de­ter­min­is­tic be­hav­ior of ap­pend­ing.

Let's say we have a func­tion which is passed a buffer, and writes some num­ber of A's to the buffer (ap­pend­ing if nec­es­sary), re­turn­ing the filled buffer:

import std.stdio;

char[] fillAs(char[] buf, size_t num)
{
   if(buf.length < num)
      buf.length = num; // increase buffer length to be able to hold the A's
   buf[0..num] = 'A';   // assign A to all the elements
   return buf[0..num];  // return the result
}

What's wrong with the fillAs func­tion? Noth­ing re­ally, but what hap­pens if in­creas­ing the length forces the buffer to be re­al­lo­cated? In that case, the buffer passed in is not over­writ­ten with A's, only the re­al­lo­cated buffer is. This can be sur­pris­ing if you were ex­pect­ing to con­tinue to use the same buffer in fur­ther op­er­a­tions, or if you ex­pected the orig­i­nal buffer to be filled with A's. The end re­sult, de­pend­ing on whether the block ref­er­enced by buf[] can be ap­pended in place, is the caller's slice might be over­writ­ten with A's, or it might not be.

// continued example...
void main()
{
   char[] str = new char[10];  // Note, the block capacity allocated for this is
                               // 15 elements
   str[] = 'B';
   fillAs(str, 20);            // buffer must be reallocated (20 > 15)
   writeln(str);               // "BBBBBBBBBB"
   fillAs(str, 12);            // buffer can be extended in place (12 <= 15)!
   writeln(str);               // "AAAAAAAAAA";
}

If you give this some thought, you should come to the con­clu­sion that such a sit­u­a­tion is un­avoid­able with­out costly copy-on-ap­pend se­man­tics -- the sys­tem can­not keep track of every slice that ref­er­ences the data, and you have to put the new data some­where. How­ever, there are a cou­ple op­tions we have to mit­i­gate the prob­lem:

  1. Re-as­sign the slice to the re­turn value of the func­tion. Note that the most im­por­tant re­sult of this func­tion is the re­turn value, not whether the buffer was used or not.
  2. Don't use the passed in buffer again. If you don't use the source slice again, then you can't ex­pe­ri­ence any is­sues with it.

As the func­tion au­thor, there are some things we can do to avoid caus­ing these prob­lems. It's im­por­tant to note that the only time this sit­u­a­tion can occur is when the func­tion ap­pends to, or in­creases the length of, a passed in slice and then writes data to the orig­i­nal por­tion of the slice. Avoid­ing this spe­cific sit­u­a­tion where pos­si­ble can re­duce the per­cep­tion of non-de­ter­min­ism. Later we will dis­cuss some prop­er­ties you can use to pre­dict how the run­time will af­fect your slice. It is a good idea to note in the doc­u­men­ta­tion how the passed in slice might or might not be over­writ­ten.

A final op­tion is to use ref to make sure the source slice is up­dated. This is some­times not an op­tion as a slice can eas­ily be an rvalue (input only). How­ever, this does not fix the prob­lem for any aliases to the same data else­where.

Caching

One of the is­sues with ap­pend­ing to a slice is that the op­er­a­tion is quick, but not quick enough. Every time we ap­pend, we need to fetch the meta­data for the block (its start­ing ad­dress, size, and used data). Doing this means an O(lg(n)) lookup in the GC's mem­ory pool for every ap­pend (not to men­tion ac­quir­ing the global GC lock). How­ever, what we want is amor­tized con­stant ap­pend­ing. To achieve this lofty goal, we em­ploy a caching tech­nique that is, as far as I know, unique to D.

Since D has the con­cept of de­fault thread local stor­age, the type sys­tem can tell us whether heap data is local to the thread (and most data is), or shared amongst all threads. Using this knowl­edge, we can achieve lock-free caching of this meta­data for thread-lo­cal ap­pends, with one cache per thread. The cache stores the most re­cent N lookups of meta­data, giv­ing us quick ac­cess to whether a slice can be ap­pended.

Slice Mem­bers and the Ap­pen­der

With D slices hav­ing such in­ter­est­ing be­hav­ior, there is a need some­times to be able to pre­dict the be­hav­ior of slices and ap­pend­ing. To that end, sev­eral prop­er­ties and meth­ods have been added to the slice.

size_t reserve(size_t n): Re­serves n el­e­ments for ap­pend­ing to a slice. If a slice can al­ready be ap­pended in place, and there is al­ready space in the array for at least n el­e­ments (n rep­re­sents both ex­ist­ing slice el­e­ments and ap­pend­able space), noth­ing is mod­i­fied. It re­turns the re­sult­ing ca­pac­ity.

int[] slice;
slice.reserve(50);
foreach(int i; 0..50)
   slice ~= i;        // does not reallocate

size_t capacity: A prop­erty which gives you the num­ber of el­e­ments the slice can hold via ap­pend­ing. If the slice can­not be ap­pended in place, this re­turns 0. Note that ca­pac­ity (if non-zero) in­cludes the cur­rent slice el­e­ments.

int[] slice = new int[5];
assert(slice.capacity == 7);  // includes the 5 pre-allocated elements
int[] slice2 = slice;
slice.length = 6;
assert(slice.capacity == 7);  // appending in place doesn't change the capacity.
assert(slice2.capacity == 0); // cannot append slice2 because it would stomp on
                              // slice's 6th element

assumeSafeAppend(): This method forces the run­time to as­sume it is safe to ap­pend a slice. Es­sen­tially this ad­justs the used field of the array to end at the same spot the slice ends.

int[] slice = new int[5];
slice = slice[0..2];
assert(slice.capacity == 0); // not safe to append, there is other valid data in the block.
slice.assumeSafeAppend();
assert(slice.capacity == 7); // force the used data to 2 elements

If D slices' ap­pend per­for­mance just isn't up to snuff for your per­for­mance re­quire­ments, there is an­other al­ter­na­tive. The std.array.Appender type will ap­pend data to an array as fast as pos­si­ble, with­out any need to look up meta­data from the run­time. Appender also sup­ports the out­put range idiom via an ap­pend op­er­a­tion (nor­mal slices only sup­port the out­put range by over­writ­ing their own data).

Con­clu­sion

Whether you are a sea­soned pro­gram­mer or a novice, the array and slice con­cepts in D pro­vide an ex­tremely rich fea­ture set that al­lows for al­most any­thing you would want to do with an array type. With a large focus on per­for­mance and us­abil­ity, the D slice type is one of those things that you don't no­tice how great it is until you work with an­other lan­guage that doesn't have it.

Thanks to David Gileadi, An­drej Mitro­vic, Jesse Phillips, Alex Dovhal, Jo­hann !Mac­Don­agh, and Jonathan Davis for their re­views and sug­ges­tions for this ar­ti­cle

© 2011-2012 by Steven Schveighof­fer
Creative Commons License
This work is li­censed under a Cre­ative Com­mons At­tri­bu­tion-NoDerivs 3.0 Un­ported Li­cense.
Forums | Comments | Search | Downloads | Home