<commit_before>package zermelo

// Sorts a []uint32 using a Radix sort.  This uses O(n) extra memory
func SortUint32(r []uint32) {
	buffer := make([]uint32, len(r))
	rsortUint32BYOB(r, buffer)
}

// Sorts a []uint64 using a Radix sort.  This uses O(n) extra memory
func SortUint64(r []uint64) {
	buffer := make([]uint64, len(r))
	rsortUint64BYOB(r, buffer)
}

// Does a radix sort in place using supplied buffer space. len(r) must equal len(buffer)
func rsortUint32BYOB(r []uint32, buffer []uint32) {
	if len(r) != len(buffer) {
		panic("You can't use a buffer of a different size")
	}
	copy(buffer, r)

	// Radix is a byte, 4 bytes to a uint32
	for pass := 0; pass < 4; pass++ {
		// Radix offset and mask
		byteOffset := uint(pass * 8)
		byteMask := uint32(0xFF << byteOffset)
		// Keep track of the number of elements for each kind of byte
		var counts [256]int
		// Keep track of where room is made for byte groups in the buffer
		var offset [256]int
		// To save allocations, switch source and buffer roles back and forth
		toBuff := pass%2 == 0

		var passByte uint8 // Current byte value
		for i := 0; i < len(r); i++ {
			// For each elem to sort, fetch the byte at current radix
			if toBuff {
				passByte = uint8((r[i] & byteMask) >> byteOffset)
			} else {
				passByte = uint8((buffer[i] & byteMask) >> byteOffset)
			}
			// inc count of bytes of this type
			counts[passByte]++
		}
		// Make room for each group of bytes by calculating offset of each
		offset[0] = 0
		for i := 1; i < len(offset); i++ {
			offset[i] = offset[i-1] + counts[i-1]
		}
		// Swap values between the buffers by radix
		for i := 0; i < len(r); i++ {
			if toBuff {
				// Get the byte of each element at the radix
				passByte = uint8((r[i] & byteMask) >> byteOffset)
				// Copy the element depending on byte offsets
				buffer[offset[passByte]] = r[i]
			} else {
				passByte = uint8((buffer[i] & byteMask) >> byteOffset)
				r[offset[passByte]] = buffer[i]
			}
			// One less space empty in that byte groups reserved area, so move the offset
			offset[passByte]++
		}
	}
}

// Does a radix sort in place using supplied buffer space. len(r) must equal len(buffer)
func rsortUint64BYOB(r []uint64, buffer []uint64) {
	if len(r) != len(buffer) {
		panic("You can't use a buffer of a different size")
	}
	copy(buffer, r)

	// Radix is a byte, 8 bytes to a uint64
	for pass := 0; pass < 8; pass++ {
		// Radix offset and mask
		byteOffset := uint(pass * 8)
		byteMask := uint64(0xFF << byteOffset)
		// Keep track of the number of elements for each kind of byte
		var counts [256]int
		// Keep track of where room is made for byte groups in the buffer
		var offset [256]int
		// To save allocations, switch source and buffer roles back and forth
		toBuff := pass%2 == 0

		var passByte uint8 // Current byte value
		for i := 0; i < len(r); i++ {
			// For each elem to sort, fetch the byte at current radix
			if toBuff {
				passByte = uint8((r[i] & byteMask) >> byteOffset)
			} else {
				passByte = uint8((buffer[i] & byteMask) >> byteOffset)
			}
			// inc count of bytes of this type
			counts[passByte]++
		}
		// Make room for each group of bytes by calculating offset of each
		offset[0] = 0
		for i := 1; i < len(offset); i++ {
			offset[i] = offset[i-1] + counts[i-1]
		}
		// Swap values between the buffers by radix
		for i := 0; i < len(r); i++ {
			if toBuff {
				// Get the byte of each element at the radix
				passByte = uint8((r[i] & byteMask) >> byteOffset)
				// Copy the element depending on byte offsets
				buffer[offset[passByte]] = r[i]
			} else {
				passByte = uint8((buffer[i] & byteMask) >> byteOffset)
				r[offset[passByte]] = buffer[i]
			}
			// One less space empty in that byte groups reserved area, so move the offset
			offset[passByte]++
		}
	}
}<commit_msg>refactoring<commit_after>package zermelo

// The radix size using during radix sorts - a byte.  Some would change this to exploit
// L1 cache optimizations, but those optimizations are not portable so we won't bother.
const RSORT_RADIX = 8

// Sorts a []uint32 using a Radix sort.  This uses O(n) extra memory
func SortUint32(r []uint32) {
	buffer := make([]uint32, len(r))
	rsortUint32BYOB(r, buffer)
}

// Sorts a []uint64 using a Radix sort.  This uses O(n) extra memory
func SortUint64(r []uint64) {
	buffer := make([]uint64, len(r))
	rsortUint64BYOB(r, buffer)
}

// Does a radix sort in place using supplied buffer space. len(r) must equal len(buffer)
func rsortUint32BYOB(r []uint32, buffer []uint32) {
	sliceCheckUint32(r, buffer)
	copy(buffer, r)

	// Radix is a byte, 4 bytes to a uint32
	for pass := uint(0); pass < 4; pass++ {
		if pass%2 == 0 { // swap back and forth between buffers to save allocations
			rsortPassUint32(r[:], buffer[:], pass)
		} else {
			rsortPassUint32(buffer[:], r[:], pass)
		}
	}
}

// Does a radix sort in place using supplied buffer space. len(r) must equal len(buffer)
func rsortUint64BYOB(r []uint64, buffer []uint64) {
	sliceCheckUint64(r, buffer)
	copy(buffer, r)

	// Radix is a byte, 8 bytes to a uint64
	for pass := uint(0); pass < 8; pass++ {
		if pass%2 == 0 { // swap back and forth between buffers to save allocations
			rsortPassUint64(r[:], buffer[:], pass)
		} else {
			rsortPassUint64(buffer[:], r[:], pass)
		}
	}
}

func rsortPassUint64(from []uint64, to []uint64, pass uint) {
	byteOffset := pass * RSORT_RADIX
	byteMask := uint64(0xFF << byteOffset)
	var counts [256]int // Keep track of the number of elements for each kind of byte
	var offset [256]int // Keep track of where room is made for byte groups in the buffer
	var passByte uint8  // Current byte value

	for i := 0; i < len(from); i++ {
		// For each elem to sort, fetch the byte at current radix
		passByte = uint8((from[i] & byteMask) >> byteOffset)
		// inc count of bytes of this type
		counts[passByte]++
	}

	// Make room for each group of bytes by calculating offset of each
	offset[0] = 0
	for i := 1; i < len(offset); i++ {
		offset[i] = offset[i-1] + counts[i-1]
	}

	// Swap values between the buffers by radix
	for i := 0; i < len(from); i++ {
		passByte = uint8((from[i] & byteMask) >> byteOffset) // Get the byte of each element at the radix
		to[offset[passByte]] = from[i]                       // Copy the element depending on byte offsets
		offset[passByte]++                                   // One less space, move the offset
	}
}

func rsortPassUint32(from []uint32, to []uint32, pass uint) {
	byteOffset := pass * RSORT_RADIX
	byteMask := uint32(0xFF << byteOffset)
	var counts [256]int // Keep track of the number of elements for each kind of byte
	var offset [256]int // Keep track of where room is made for byte groups in the buffer
	var passByte uint8  // Current byte value

	for _, elem := range from {
		// For each elem to sort, fetch the byte at current radix
		passByte = uint8((elem & byteMask) >> byteOffset)
		// inc count of bytes of this type
		counts[passByte]++
	}

	// Make room for each group of bytes by calculating offset of each
	offset[0] = 0
	for i := 1; i < len(offset); i++ {
		offset[i] = offset[i-1] + counts[i-1]
	}

	// Swap values between the buffers by radix
	for i := 0; i < len(from); i++ {
		passByte = uint8((from[i] & byteMask) >> byteOffset) // Get the byte of each element at the radix
		to[offset[passByte]] = from[i]                       // Copy the element depending on byte offsets
		offset[passByte]++                                   // One less space, move the offset
	}
}

func sliceCheckUint64(a []uint64, b []uint64) {
	if a == nil || b == nil || len(a) != len(b) {
		panic ("Slices must be the same size and not nil")
	}
}

func sliceCheckUint32(a []uint32, b []uint32) {
	if a == nil || b == nil || len(a) != len(b) {
		panic ("Slices must be the same size and not nil")
	}
}

{'fraction_non_alphanumeric': 0.12387329384496523, 'fraction_numerical': 0.027169714138552667, 'mean_word_length': 3.0707547169811322, 'pattern_counts': {'":': 0, '<': 26, '<?xml version=': 0, '>': 27, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 2, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '701205', 'n_tokens_mistral': 2901, 'n_tokens_neox': 2591, 'n_words': 1013}