| 75 | == Summary of Deletion Methods == |

| 76 | |

| 77 | === Parallel Prefix Deletion === |

| 78 | |

| 79 | This method uses only bitwise logic and shifting to perform deletion. |

| 80 | For deletion within 2^k bit fields, k steps are required. Each step i |

| 81 | involves application of a mask to select of bits to move 2^i positions. |

| 82 | 4 operations are required per step. |

| 83 | However, the calculation of masks requires k^2 preprocessing steps. |

| 84 | However, when applied to deletion of data from several parallel bit streams, the |

| 85 | preprocessing cost is shared across the streams. |

| 86 | |

| 87 | === Deletion by Left Result Induction === |

| 88 | |

| 89 | In this method, deletion steps ensure that results are leftmost within |

| 90 | fields of size 2^i at step i. The process involves SIMD multiplication |

| 91 | operations at each step. |

| 92 | |

| 93 | === Deletion by Central Result Induction === |

| 94 | |

| 95 | In this method, deletion steps produce results that span or touch the |

| 96 | centre position of each 2^(i+1) bit field at step i. The process |

| 97 | involves SIMD rotate operations at each step. |

| 98 | |

| 99 | === Deletion by PEXT === |

| 100 | |

| 101 | Intel introduced the PEXT instruction with its Haswell processors. |

| 102 | This operation uses a mask to select nondeleted bits of a 64-bit value |

| 103 | and compress them together leftmost in a 64-bit result. Thus it performs |

| 104 | parallel deletion in a single step, with a mask that is the inverse of the |

| 105 | deletion mask. |

| 106 | |

| 107 | === Deletion by Permutation Vector Computation === |

| 108 | |

| 109 | This method is suitable for performing deletion at byte or large granularities, |

| 110 | given a processor supporting shuffle or permutation operations with variable selectors. |