Created
August 24, 2016 04:59
-
-
Save manofstick/c9181594a9dbac170b01ce9ae14f3b2d to your computer and use it in GitHub Desktop.
Fast filtering
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| let boolToUInt32 (b:bool) = (# "conv.u4" (# "cgt.un" b 0 : int32 #) : uint32 #) | |
| module internal Filter = | |
| [<Struct; NoComparison; NoEquality>] | |
| type MaskStruct = | |
| val mutable _0x00 : bool | |
| val mutable _0x01 : bool | |
| val mutable _0x02 : bool | |
| val mutable _0x03 : bool | |
| val mutable _0x04 : bool | |
| val mutable _0x05 : bool | |
| val mutable _0x06 : bool | |
| val mutable _0x07 : bool | |
| val mutable _0x08 : bool | |
| val mutable _0x09 : bool | |
| val mutable _0x0A : bool | |
| val mutable _0x0B : bool | |
| val mutable _0x0C : bool | |
| val mutable _0x0D : bool | |
| val mutable _0x0E : bool | |
| val mutable _0x0F : bool | |
| val mutable _0x10 : bool | |
| val mutable _0x11 : bool | |
| val mutable _0x12 : bool | |
| val mutable _0x13 : bool | |
| val mutable _0x14 : bool | |
| val mutable _0x15 : bool | |
| val mutable _0x16 : bool | |
| val mutable _0x17 : bool | |
| val mutable _0x18 : bool | |
| val mutable _0x19 : bool | |
| val mutable _0x1A : bool | |
| val mutable _0x1B : bool | |
| val mutable _0x1C : bool | |
| val mutable _0x1D : bool | |
| val mutable _0x1E : bool | |
| val mutable _0x1F : bool | |
| let populateMaskStruct f (array:array<_>) arrayBaseIdx (fd:byref<MaskStruct>) = | |
| fd._0x00 <- f array.[arrayBaseIdx+0x00] | |
| fd._0x01 <- f array.[arrayBaseIdx+0x01] | |
| fd._0x02 <- f array.[arrayBaseIdx+0x02] | |
| fd._0x03 <- f array.[arrayBaseIdx+0x03] | |
| fd._0x04 <- f array.[arrayBaseIdx+0x04] | |
| fd._0x05 <- f array.[arrayBaseIdx+0x05] | |
| fd._0x06 <- f array.[arrayBaseIdx+0x06] | |
| fd._0x07 <- f array.[arrayBaseIdx+0x07] | |
| fd._0x08 <- f array.[arrayBaseIdx+0x08] | |
| fd._0x09 <- f array.[arrayBaseIdx+0x09] | |
| fd._0x0A <- f array.[arrayBaseIdx+0x0A] | |
| fd._0x0B <- f array.[arrayBaseIdx+0x0B] | |
| fd._0x0C <- f array.[arrayBaseIdx+0x0C] | |
| fd._0x0D <- f array.[arrayBaseIdx+0x0D] | |
| fd._0x0E <- f array.[arrayBaseIdx+0x0E] | |
| fd._0x0F <- f array.[arrayBaseIdx+0x0F] | |
| fd._0x10 <- f array.[arrayBaseIdx+0x10] | |
| fd._0x11 <- f array.[arrayBaseIdx+0x11] | |
| fd._0x12 <- f array.[arrayBaseIdx+0x12] | |
| fd._0x13 <- f array.[arrayBaseIdx+0x13] | |
| fd._0x14 <- f array.[arrayBaseIdx+0x14] | |
| fd._0x15 <- f array.[arrayBaseIdx+0x15] | |
| fd._0x16 <- f array.[arrayBaseIdx+0x16] | |
| fd._0x17 <- f array.[arrayBaseIdx+0x17] | |
| fd._0x18 <- f array.[arrayBaseIdx+0x18] | |
| fd._0x19 <- f array.[arrayBaseIdx+0x19] | |
| fd._0x1A <- f array.[arrayBaseIdx+0x1A] | |
| fd._0x1B <- f array.[arrayBaseIdx+0x1B] | |
| fd._0x1C <- f array.[arrayBaseIdx+0x1C] | |
| fd._0x1D <- f array.[arrayBaseIdx+0x1D] | |
| fd._0x1E <- f array.[arrayBaseIdx+0x1E] | |
| fd._0x1F <- f array.[arrayBaseIdx+0x1F] | |
| let calculateMask (fd:byref<MaskStruct>) = | |
| let mutable mask = | |
| ((LanguagePrimitives.boolToUInt32 fd._0x00) <<< 0x00) | |
| mask <- mask ||| ((LanguagePrimitives.boolToUInt32 fd._0x01) <<< 0x01) | |
| mask <- mask ||| ((LanguagePrimitives.boolToUInt32 fd._0x02) <<< 0x02) | |
| mask <- mask ||| ((LanguagePrimitives.boolToUInt32 fd._0x03) <<< 0x03) | |
| mask <- mask ||| ((LanguagePrimitives.boolToUInt32 fd._0x04) <<< 0x04) | |
| mask <- mask ||| ((LanguagePrimitives.boolToUInt32 fd._0x05) <<< 0x05) | |
| mask <- mask ||| ((LanguagePrimitives.boolToUInt32 fd._0x06) <<< 0x06) | |
| mask <- mask ||| ((LanguagePrimitives.boolToUInt32 fd._0x07) <<< 0x07) | |
| mask <- mask ||| ((LanguagePrimitives.boolToUInt32 fd._0x08) <<< 0x08) | |
| mask <- mask ||| ((LanguagePrimitives.boolToUInt32 fd._0x09) <<< 0x09) | |
| mask <- mask ||| ((LanguagePrimitives.boolToUInt32 fd._0x0A) <<< 0x0A) | |
| mask <- mask ||| ((LanguagePrimitives.boolToUInt32 fd._0x0B) <<< 0x0B) | |
| mask <- mask ||| ((LanguagePrimitives.boolToUInt32 fd._0x0C) <<< 0x0C) | |
| mask <- mask ||| ((LanguagePrimitives.boolToUInt32 fd._0x0D) <<< 0x0D) | |
| mask <- mask ||| ((LanguagePrimitives.boolToUInt32 fd._0x0E) <<< 0x0E) | |
| mask <- mask ||| ((LanguagePrimitives.boolToUInt32 fd._0x0F) <<< 0x0F) | |
| mask <- mask ||| ((LanguagePrimitives.boolToUInt32 fd._0x10) <<< 0x10) | |
| mask <- mask ||| ((LanguagePrimitives.boolToUInt32 fd._0x11) <<< 0x11) | |
| mask <- mask ||| ((LanguagePrimitives.boolToUInt32 fd._0x12) <<< 0x12) | |
| mask <- mask ||| ((LanguagePrimitives.boolToUInt32 fd._0x13) <<< 0x13) | |
| mask <- mask ||| ((LanguagePrimitives.boolToUInt32 fd._0x14) <<< 0x14) | |
| mask <- mask ||| ((LanguagePrimitives.boolToUInt32 fd._0x15) <<< 0x15) | |
| mask <- mask ||| ((LanguagePrimitives.boolToUInt32 fd._0x16) <<< 0x16) | |
| mask <- mask ||| ((LanguagePrimitives.boolToUInt32 fd._0x17) <<< 0x17) | |
| mask <- mask ||| ((LanguagePrimitives.boolToUInt32 fd._0x18) <<< 0x18) | |
| mask <- mask ||| ((LanguagePrimitives.boolToUInt32 fd._0x19) <<< 0x19) | |
| mask <- mask ||| ((LanguagePrimitives.boolToUInt32 fd._0x1A) <<< 0x1A) | |
| mask <- mask ||| ((LanguagePrimitives.boolToUInt32 fd._0x1B) <<< 0x1B) | |
| mask <- mask ||| ((LanguagePrimitives.boolToUInt32 fd._0x1C) <<< 0x1C) | |
| mask <- mask ||| ((LanguagePrimitives.boolToUInt32 fd._0x1D) <<< 0x1D) | |
| mask <- mask ||| ((LanguagePrimitives.boolToUInt32 fd._0x1E) <<< 0x1E) | |
| mask ||| ((LanguagePrimitives.boolToUInt32 fd._0x1F) <<< 0x1F) | |
| let createMask f (array:array<_>) = | |
| let thirtytooth = array.Length/32 | |
| let filterMaskMap = Array.zeroCreateUnchecked<uint32> (thirtytooth+1) | |
| let mutable filteredCount = 0 | |
| let mutable filterMaskMapIdx = 0 | |
| let mutable fd = Unchecked.defaultof<MaskStruct> | |
| while filterMaskMapIdx < thirtytooth do | |
| populateMaskStruct f array (filterMaskMapIdx*32) &fd | |
| let mask = calculateMask &fd | |
| if mask <> 0u then | |
| filteredCount <- filteredCount + int (fastGetBitsCount mask) | |
| filterMaskMap.[filterMaskMapIdx] <- mask | |
| filterMaskMapIdx <- filterMaskMapIdx + 1 | |
| let arrayIdx = filterMaskMapIdx*32 | |
| if arrayIdx < array.Length then | |
| let mutable filterMask = 0u | |
| let mutable offset = 0 | |
| for arrayIdx = arrayIdx to array.Length-1 do | |
| filterMask <- filterMask ||| (LanguagePrimitives.boolToUInt32 (f array.[arrayIdx]) <<< offset) | |
| offset <- offset + 1 | |
| filteredCount <- filteredCount + int (fastGetBitsCount filterMask) | |
| filterMaskMap.[filterMaskMap.Length-1] <- filterMask | |
| filterMaskMap, filteredCount | |
| let createAndPopulate (filterMaskMap:array<uint32>,filteredCount) (src:array<_>) = | |
| let dst = Array.zeroCreateUnchecked filteredCount | |
| let mutable dstIdx = 0 | |
| let mutable srcIdx = 0 | |
| for mask in filterMaskMap do | |
| if mask <> 0u then | |
| if (mask &&& (1u<<<0x00)) <> 0u then dst.[dstIdx] <- src.[srcIdx+0x00]; dstIdx <- dstIdx + 1 | |
| if (mask &&& (1u<<<0x01)) <> 0u then dst.[dstIdx] <- src.[srcIdx+0x01]; dstIdx <- dstIdx + 1 | |
| if (mask &&& (1u<<<0x02)) <> 0u then dst.[dstIdx] <- src.[srcIdx+0x02]; dstIdx <- dstIdx + 1 | |
| if (mask &&& (1u<<<0x03)) <> 0u then dst.[dstIdx] <- src.[srcIdx+0x03]; dstIdx <- dstIdx + 1 | |
| if (mask &&& (1u<<<0x04)) <> 0u then dst.[dstIdx] <- src.[srcIdx+0x04]; dstIdx <- dstIdx + 1 | |
| if (mask &&& (1u<<<0x05)) <> 0u then dst.[dstIdx] <- src.[srcIdx+0x05]; dstIdx <- dstIdx + 1 | |
| if (mask &&& (1u<<<0x06)) <> 0u then dst.[dstIdx] <- src.[srcIdx+0x06]; dstIdx <- dstIdx + 1 | |
| if (mask &&& (1u<<<0x07)) <> 0u then dst.[dstIdx] <- src.[srcIdx+0x07]; dstIdx <- dstIdx + 1 | |
| if (mask &&& (1u<<<0x08)) <> 0u then dst.[dstIdx] <- src.[srcIdx+0x08]; dstIdx <- dstIdx + 1 | |
| if (mask &&& (1u<<<0x09)) <> 0u then dst.[dstIdx] <- src.[srcIdx+0x09]; dstIdx <- dstIdx + 1 | |
| if (mask &&& (1u<<<0x0A)) <> 0u then dst.[dstIdx] <- src.[srcIdx+0x0A]; dstIdx <- dstIdx + 1 | |
| if (mask &&& (1u<<<0x0B)) <> 0u then dst.[dstIdx] <- src.[srcIdx+0x0B]; dstIdx <- dstIdx + 1 | |
| if (mask &&& (1u<<<0x0C)) <> 0u then dst.[dstIdx] <- src.[srcIdx+0x0C]; dstIdx <- dstIdx + 1 | |
| if (mask &&& (1u<<<0x0D)) <> 0u then dst.[dstIdx] <- src.[srcIdx+0x0D]; dstIdx <- dstIdx + 1 | |
| if (mask &&& (1u<<<0x0E)) <> 0u then dst.[dstIdx] <- src.[srcIdx+0x0E]; dstIdx <- dstIdx + 1 | |
| if (mask &&& (1u<<<0x0F)) <> 0u then dst.[dstIdx] <- src.[srcIdx+0x0F]; dstIdx <- dstIdx + 1 | |
| if (mask &&& (1u<<<0x10)) <> 0u then dst.[dstIdx] <- src.[srcIdx+0x10]; dstIdx <- dstIdx + 1 | |
| if (mask &&& (1u<<<0x11)) <> 0u then dst.[dstIdx] <- src.[srcIdx+0x11]; dstIdx <- dstIdx + 1 | |
| if (mask &&& (1u<<<0x12)) <> 0u then dst.[dstIdx] <- src.[srcIdx+0x12]; dstIdx <- dstIdx + 1 | |
| if (mask &&& (1u<<<0x13)) <> 0u then dst.[dstIdx] <- src.[srcIdx+0x13]; dstIdx <- dstIdx + 1 | |
| if (mask &&& (1u<<<0x14)) <> 0u then dst.[dstIdx] <- src.[srcIdx+0x14]; dstIdx <- dstIdx + 1 | |
| if (mask &&& (1u<<<0x15)) <> 0u then dst.[dstIdx] <- src.[srcIdx+0x15]; dstIdx <- dstIdx + 1 | |
| if (mask &&& (1u<<<0x16)) <> 0u then dst.[dstIdx] <- src.[srcIdx+0x16]; dstIdx <- dstIdx + 1 | |
| if (mask &&& (1u<<<0x17)) <> 0u then dst.[dstIdx] <- src.[srcIdx+0x17]; dstIdx <- dstIdx + 1 | |
| if (mask &&& (1u<<<0x18)) <> 0u then dst.[dstIdx] <- src.[srcIdx+0x18]; dstIdx <- dstIdx + 1 | |
| if (mask &&& (1u<<<0x19)) <> 0u then dst.[dstIdx] <- src.[srcIdx+0x19]; dstIdx <- dstIdx + 1 | |
| if (mask &&& (1u<<<0x1A)) <> 0u then dst.[dstIdx] <- src.[srcIdx+0x1A]; dstIdx <- dstIdx + 1 | |
| if (mask &&& (1u<<<0x1B)) <> 0u then dst.[dstIdx] <- src.[srcIdx+0x1B]; dstIdx <- dstIdx + 1 | |
| if (mask &&& (1u<<<0x1C)) <> 0u then dst.[dstIdx] <- src.[srcIdx+0x1C]; dstIdx <- dstIdx + 1 | |
| if (mask &&& (1u<<<0x1D)) <> 0u then dst.[dstIdx] <- src.[srcIdx+0x1D]; dstIdx <- dstIdx + 1 | |
| if (mask &&& (1u<<<0x1E)) <> 0u then dst.[dstIdx] <- src.[srcIdx+0x1E]; dstIdx <- dstIdx + 1 | |
| if (mask &&& (1u<<<0x1F)) <> 0u then dst.[dstIdx] <- src.[srcIdx+0x1F]; dstIdx <- dstIdx + 1 | |
| srcIdx <- srcIdx + 32 | |
| dst | |
| [<CompiledName("Filter")>] | |
| let filter f (array: _[]) = | |
| checkNonNull "array" array | |
| match array |> Filter.createMask f with | |
| | _, 0 -> empty | |
| | _, count when count = array.Length -> array.Clone () :?> _ | |
| | mask -> array |> Filter.createAndPopulate mask |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment