Skip to content

Commit 5d20844

Browse files
escesc
authored
Merge pull request #1 from esc/typed_list_delete_slice
Typed list delete slice
2 parents adec894 + 488d6c0 commit 5d20844

8 files changed

Lines changed: 526 additions & 21 deletions

File tree

‎numba/_helpermod.c‎

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -149,6 +149,7 @@ build_c_helpers_dict(void)
149149
declmethod(list_getitem);
150150
declmethod(list_append);
151151
declmethod(list_pop);
152+
declmethod(list_delete_slice);
152153
declmethod(list_iter_sizeof);
153154
declmethod(list_iter);
154155
declmethod(list_iter_next);

‎numba/_listobject.c‎

Lines changed: 252 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -1,10 +1,12 @@
11
#include "_listobject.h"
22

33
/* This implements the C component of the Numba typed list. It is loosely
4-
* inspired by the list implementation of the cpython list. The exact commit
5-
* is:
4+
* inspired by the list implementation of the cpython list with some parts
5+
* taken from the cpython slice implementation. The exact commit-id of the
6+
* relevant files are:
67
*
78
* https://github.com/python/cpython/blob/51ddab8dae056867f3595ab3400bffc93f67c8d4/Objects/listobject.c
9+
* https://github.com/python/cpython/blob/51ddab8dae056867f3595ab3400bffc93f67c8d4/Objects/sliceobject.c
810
*
911
* Algorithmically, this list is very similar to the cpython implementation so
1012
* it should have the same performance (Big-O) characteristics for accessing,
@@ -32,8 +34,9 @@
3234
* - Setting an item numba_list_getitem
3335
* - Poping an item numba_list_pop
3436
* - Resizing the list numba_list_resize
37+
* - Deleting a slice numba_list_delete_slice
3538
*
36-
* As you can see, no functions related to slicing have been implemented. This
39+
* As you can see, only a single function for slices is implemented. The rest
3740
* is all done entirely at the compiler level which then calls the c functions
3841
* to mutate the list accordingly. Since slicing allows for replace, insert and
3942
* delete operations over multiple items, we can simply implement those using
@@ -384,6 +387,106 @@ numba_list_resize(NB_List *lp, Py_ssize_t newsize) {
384387
return LIST_OK;
385388
}
386389

390+
/* Delete a slice
391+
*
392+
* start: the start index of ths slice
393+
* stop: the stop index of the slice (not included)
394+
* step: the step to take
395+
*
396+
* This function assumes that the start and stop were clipped appropriately.
397+
* I.e. if step > 0 start >= 0 and stop <= len(l) and
398+
* if step < 0 start <= length and stop >= -1
399+
* step != 0 and no Python negative indexing allowed.
400+
*
401+
* This code was copied and edited from the relevant section in
402+
* list_ass_subscript from the cpython implementation, see the top of this file
403+
* for the exact source
404+
*/
405+
int
406+
numba_list_delete_slice(NB_List *lp,
407+
Py_ssize_t start, Py_ssize_t stop, Py_ssize_t step) {
408+
int result, i, slicelength, new_length;
409+
char *loc, *new_loc;
410+
Py_ssize_t leftover_bytes, cur, lim;
411+
// calculate the slicelength, taken from PySlice_AdjustIndices, see the top
412+
// of this file for the exact source
413+
if (step > 0) {
414+
slicelength = start < stop ? (stop - start - 1) / step + 1 : 0;
415+
} else {
416+
slicelength = stop < start ? (start - stop - 1) / -step + 1 : 0;
417+
}
418+
if (slicelength <= 0){
419+
return LIST_OK;
420+
}
421+
new_length = lp->size - slicelength;
422+
// reverse step and indices
423+
if (step < 0) {
424+
stop = start + 1;
425+
start = stop + step * (slicelength - 1) - 1;
426+
step = -step;
427+
}
428+
if (step == 1) {
429+
// decref if needed
430+
if (lp->methods.item_decref) {
431+
for (i = start ; i < stop ; i++){
432+
loc = lp->items + lp->item_size * i;
433+
lp->methods.item_decref(loc);
434+
}
435+
}
436+
// memove items into place
437+
leftover_bytes = (lp->size - stop) * lp->item_size;
438+
loc = lp->items + lp->item_size * start;
439+
new_loc = lp->items + lp->item_size * stop;
440+
memmove(loc, new_loc, leftover_bytes);
441+
}
442+
else { // step != 1
443+
/* drawing pictures might help understand these for
444+
* loops. Basically, we memmove the parts of the
445+
* list that are *not* part of the slice: step-1
446+
* items for each item that is part of the slice,
447+
* and then tail end of the list that was not
448+
* covered by the slice
449+
*
450+
* */
451+
for (cur = start, // index of item to be deleted
452+
i = 0; // counter of total items deleted so far
453+
cur < stop;
454+
cur += step,
455+
i++) {
456+
lim = step - 1; // number of leftover items after deletion of item
457+
// clip limit, in case we are at the end of the slice, and there
458+
// are now less than step-1 items to be moved
459+
if (cur + step >= lp->size) {
460+
lim = lp->size - cur - 1;
461+
}
462+
// decref item being removed
463+
loc = lp->items + lp->item_size * cur;
464+
list_decref_item(lp, loc);
465+
/* memmove the aforementiond step-1 (or less) items
466+
* dst : index of deleted item minus total deleted sofar
467+
* src : index of deleted item plus one (next item)
468+
*/
469+
memmove(lp->items + lp->item_size * (cur - i),
470+
lp->items + lp->item_size * (cur + 1),
471+
lim * lp->item_size);
472+
}
473+
// memmove tail of the list
474+
cur = start + slicelength * step;
475+
if (cur < lp->size) {
476+
memmove(lp->items + lp->item_size * (cur - slicelength),
477+
lp->items + lp->item_size * cur,
478+
(lp->size - cur) * lp->item_size);
479+
}
480+
}
481+
// resize to correct size
482+
result = numba_list_resize(lp, new_length);
483+
if(result < LIST_OK) {
484+
// Since we are decreasing the size, this should never happen
485+
return result;
486+
}
487+
return LIST_OK;
488+
}
489+
387490

388491
/* Return the size of the list iterator (NB_ListIter) struct.
389492
*/
@@ -446,6 +549,7 @@ numba_test_list(void) {
446549
NB_ListIter iter;
447550
char got_item[4] = "\x00\x00\x00\x00";
448551
const char *test_items_1 = NULL, *test_items_2 = NULL;
552+
char *test_items_3 = NULL;
449553
puts("test_list");
450554

451555

@@ -610,11 +714,156 @@ numba_test_list(void) {
610714
case 1: CHECK(lp->allocated == 0); break;
611715
}
612716
}
717+
// free existing list
718+
numba_list_free(lp);
719+
720+
721+
// Setup list for testing delete_slice
722+
status = numba_list_new(&lp, 1, 0);
723+
CHECK(status == LIST_OK);
724+
CHECK(lp->item_size == 1);
725+
CHECK(lp->size == 0);
726+
CHECK(lp->allocated == 0);
727+
for (i = 0; i < 17 ; i++) {
728+
status = numba_list_append(lp, (const char*)&i);
729+
CHECK(status == LIST_OK);
730+
}
731+
CHECK(lp->size == 17);
732+
test_items_3 = "\x00\x01\x02\x03\x04\x05\x06\x07\x08\x09\x0a\x0b\x0c\x0d\x0e\x0f\x10";
733+
CHECK(memcmp(lp->items, test_items_3, 17) == 0);
734+
735+
// delete multiple elements from the middle
736+
status = numba_list_delete_slice(lp, 2, 5, 1);
737+
CHECK(status == LIST_OK);
738+
CHECK(lp->size == 14);
739+
test_items_3 = "\x00\x01\x05\x06\x07\x08\x09\x0a\x0b\x0c\x0d\x0e\x0f\x10";
740+
CHECK(memcmp(lp->items, test_items_3, 14) == 0);
741+
742+
// delete single element from start
743+
status = numba_list_delete_slice(lp, 0, 1, 1);
744+
CHECK(status == LIST_OK);
745+
CHECK(lp->size == 13);
746+
test_items_3 = "\x01\x05\x06\x07\x08\x09\x0a\x0b\x0c\x0d\x0e\x0f\x10";
747+
CHECK(memcmp(lp->items, test_items_3, 13) == 0);
748+
749+
// delete single element from end
750+
status = numba_list_delete_slice(lp, 12, 13, 1);
751+
CHECK(status == LIST_OK);
752+
CHECK(lp->size == 12);
753+
test_items_3 = "\x01\x05\x06\x07\x08\x09\x0a\x0b\x0c\x0d\x0e\x0f";
754+
CHECK(memcmp(lp->items, test_items_3, 12) == 0);
755+
756+
// delete single element from middle
757+
status = numba_list_delete_slice(lp, 4, 5, 1);
758+
CHECK(status == LIST_OK);
759+
CHECK(lp->size == 11);
760+
test_items_3 = "\x01\x05\x06\x07\x09\x0a\x0b\x0c\x0d\x0e\x0f";
761+
CHECK(memcmp(lp->items, test_items_3, 11) == 0);
762+
763+
// delete all elements except first and last
764+
status = numba_list_delete_slice(lp, 1, 10, 1);
765+
CHECK(status == LIST_OK);
766+
CHECK(lp->size == 2);
767+
test_items_3 = "\x01\x0f";
768+
CHECK(memcmp(lp->items, test_items_3, 2) == 0);
769+
770+
// delete all remaining elements
771+
status = numba_list_delete_slice(lp, 0, lp->size, 1);
772+
CHECK(status == LIST_OK);
773+
CHECK(lp->size == 0);
774+
test_items_3 = "";
775+
CHECK(memcmp(lp->items, test_items_3, 0) == 0);
776+
777+
// free existing list
778+
numba_list_free(lp);
779+
780+
// Setup list for testing delete_slice with non unary step
781+
status = numba_list_new(&lp, 1, 0);
782+
CHECK(status == LIST_OK);
783+
CHECK(lp->item_size == 1);
784+
CHECK(lp->size == 0);
785+
CHECK(lp->allocated == 0);
786+
for (i = 0; i < 17 ; i++) {
787+
status = numba_list_append(lp, (const char*)&i);
788+
CHECK(status == LIST_OK);
789+
}
790+
CHECK(lp->size == 17);
791+
792+
// delete all items with odd index
793+
status = numba_list_delete_slice(lp, 0, 17, 2);
794+
CHECK(status == LIST_OK);
795+
CHECK(lp->size == 8);
796+
test_items_3 = "\x01\x03\x05\x07\x09\x0b\x0d\x0f";
797+
CHECK(memcmp(lp->items, test_items_3, 8) == 0);
798+
799+
// delete with a step of 4, starting at index 1
800+
status = numba_list_delete_slice(lp, 1, 8, 4);
801+
CHECK(status == LIST_OK);
802+
CHECK(lp->size == 6);
803+
test_items_3 = "\x01\x05\x07\x09\x0d\x0f";
804+
CHECK(memcmp(lp->items, test_items_3, 6) == 0);
805+
806+
// delete with a step of 2, but finish before end of list
807+
status = numba_list_delete_slice(lp, 0, 4, 2);
808+
CHECK(status == LIST_OK);
809+
CHECK(lp->size == 4);
810+
test_items_3 = "\x05\x09\x0d\x0f";
811+
CHECK(memcmp(lp->items, test_items_3, 4) == 0);
812+
813+
// no-op on empty slice
814+
status = numba_list_delete_slice(lp, 0, 0, 1);
815+
CHECK(status == LIST_OK);
816+
CHECK(lp->size == 4);
817+
test_items_3 = "\x05\x09\x0d\x0f";
818+
CHECK(memcmp(lp->items, test_items_3, 4) == 0);
819+
820+
// no-op on empty slice, non-zero index
821+
status = numba_list_delete_slice(lp, 2, 2, 1);
822+
CHECK(status == LIST_OK);
823+
CHECK(lp->size == 4);
824+
test_items_3 = "\x05\x09\x0d\x0f";
825+
CHECK(memcmp(lp->items, test_items_3, 4) == 0);
826+
827+
// free list and return 0
828+
numba_list_free(lp);
829+
830+
// Setup list for testing delete_slice with negative step
831+
status = numba_list_new(&lp, 1, 0);
832+
CHECK(status == LIST_OK);
833+
CHECK(lp->item_size == 1);
834+
CHECK(lp->size == 0);
835+
CHECK(lp->allocated == 0);
836+
for (i = 0; i < 17 ; i++) {
837+
status = numba_list_append(lp, (const char*)&i);
838+
CHECK(status == LIST_OK);
839+
}
840+
CHECK(lp->size == 17);
841+
842+
// delete all items using unary negative slice
843+
status = numba_list_delete_slice(lp, 16, -1, -1);
844+
CHECK(status == LIST_OK);
845+
CHECK(lp->size == 0);
846+
847+
// refill list
848+
for (i = 0; i < 17 ; i++) {
849+
status = numba_list_append(lp, (const char*)&i);
850+
CHECK(status == LIST_OK);
851+
}
852+
853+
// delete all items using unary negative slice
854+
// need to start at index of last item (16) and
855+
// go beyond first item, i.e. -1 in Cd
856+
status = numba_list_delete_slice(lp, 16, -1, -2);
857+
CHECK(status == LIST_OK);
858+
CHECK(lp->size == 8);
859+
test_items_3 = "\x01\x03\x05\x07\x09\x0b\x0d\x0f";
860+
CHECK(memcmp(lp->items, test_items_3, 8) == 0);
613861

614862
// free list and return 0
615863
numba_list_free(lp);
616864
return 0;
617865

866+
618867
}
619868

620869
#undef CHECK

‎numba/_listobject.h‎

Lines changed: 4 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -85,6 +85,10 @@ numba_list_pop(NB_List *lp, Py_ssize_t index, char *out);
8585
NUMBA_EXPORT_FUNC(int)
8686
numba_list_resize(NB_List *lp, Py_ssize_t newsize);
8787

88+
NUMBA_EXPORT_FUNC(int)
89+
numba_list_delete_slice(NB_List *lp,
90+
Py_ssize_t start, Py_ssize_t stop, Py_ssize_t step);
91+
8892
NUMBA_EXPORT_FUNC(size_t)
8993
numba_list_iter_sizeof(void);
9094

‎numba/listobject.py‎

Lines changed: 39 additions & 12 deletions
Original file line numberDiff line numberDiff line change
@@ -688,16 +688,8 @@ def impl_slice(l, index, item):
688688
slice_range.start + len(item))
689689
for i,j in zip(replace_range, item):
690690
l[i] = j
691-
# pop the remaining ones
692-
pop_range = range(slice_range.start + len(item),
693-
slice_range.stop)
694-
# pop will mutate the list, so we always need to pop the
695-
# same index
696-
k = slice_range.start + len(item)
697-
for _ in pop_range:
698-
# FIXME: This may be slow. Each pop can incur a
699-
# memory copy of one or more items.
700-
l.pop(k)
691+
# delete remaining ones
692+
del l[slice_range.start + len(item):slice_range.stop]
701693
# Extended slices
702694
else:
703695
if len(slice_range) != len(item):
@@ -739,6 +731,38 @@ def impl(l, index=-1):
739731
raise TypingError("argument for pop must be a signed integer")
740732

741733

734+
@intrinsic
735+
def _list_delete_slice(typingctx, l, start, stop, step):
736+
"""Wrap numba_list_delete_slice
737+
"""
738+
resty = types.int32
739+
sig = resty(l, start, stop, step)
740+
741+
def codegen(context, builder, sig, args):
742+
fnty = ir.FunctionType(
743+
ll_status,
744+
[ll_list_type, ll_ssize_t, ll_ssize_t, ll_ssize_t],
745+
)
746+
[l, start, stop, step] = args
747+
[tl, tstart, tstop, tstep] = sig.args
748+
fn = builder.module.get_or_insert_function(fnty,
749+
name='numba_list_delete_slice')
750+
751+
lp = _container_get_data(context, builder, tl, l)
752+
status = builder.call(
753+
fn,
754+
[
755+
lp,
756+
start,
757+
stop,
758+
step,
759+
],
760+
)
761+
return status
762+
763+
return sig, codegen
764+
765+
742766
@overload(operator.delitem)
743767
def impl_delitem(l, index):
744768
if not isinstance(l, types.ListType):
@@ -752,8 +776,11 @@ def integer_impl(l, index):
752776

753777
elif isinstance(index, types.SliceType):
754778
def slice_impl(l, index):
755-
raise NotImplementedError
756-
779+
slice_range = handle_slice(l, index)
780+
_list_delete_slice(l,
781+
slice_range.start,
782+
slice_range.stop,
783+
slice_range.step)
757784
return slice_impl
758785

759786
else:

0 commit comments

Comments
 (0)