Repository: microsoft/garnet
File: libs/server/Objects/Set/SetObjectImpl.cs (C#)

Code before:

            int countDone = 0;
            bool isMemory = false;
            MemoryHandle ptrHandle = default;
            byte* ptr = output.SpanByte.ToPointer();

            var curr = ptr;
            var end = curr + output.Length;

            ObjectOutputHeader _output = default;

            try
            {
                if (count > 0)
                {
                    // Return an array of distinct elements
                    var countParameter = count > set.Count ? set.Count : count;
                    List<byte[]> randomElements = new List<byte[]>();

                    // Write the size of the array reply
                    while (!RespWriteUtils.WriteArrayLength(countParameter, ref curr, end))
                        ObjectUtils.ReallocateOutput(ref output, ref isMemory, ref ptr, ref ptrHandle, ref curr, ref end);

                    while (randomElements.Count < countParameter)
                    {
                        int index = RandomNumberGenerator.GetInt32(0, set.Count);
                        var item = set.ElementAt(index);
                        if (!randomElements.Any(x => x.SequenceEqual(item)))
                        {
                            randomElements.Add(item);
                            while (!RespWriteUtils.WriteBulkString(item, ref curr, end))
                                ObjectUtils.ReallocateOutput(ref output, ref isMemory, ref ptr, ref ptrHandle, ref curr, ref end);
                        }
                        countDone++;
                    }
                    countDone += count - countParameter;
                }
                else if (count == int.MinValue) // no count parameter is present
                {
                    // Return a single random element from the set
                    if (set.Count > 0)
                    {
                        int index = RandomNumberGenerator.GetInt32(0, set.Count);
                        var item = set.ElementAt(index);
                        while (!RespWriteUtils.WriteBulkString(item, ref curr, end))
                            ObjectUtils.ReallocateOutput(ref output, ref isMemory, ref ptr, ref ptrHandle, ref curr, ref end);
                    }
                    else
                    {
                        // If set is empty, return nil
                        while (!RespWriteUtils.WriteDirect(CmdStrings.RESP_ERRNOTFOUND, ref curr, end))

Review comment (performance):
This is a bit inefficient, once you get a random index, you need to get it from the set (O(M)) and compare it to all the other elements (O(n*m)), and you do that n times. Collectively you get O(M*m*n^2), where M is the set size, m is the max length in the set and n is the count, so worse case would be O(m*M^3) if n == m.

Consider the following solution - generate a set of n non-repeating random indexes (O(n)), sort it (O(nlogn)) and then iterate over the target set object, check if the index is in the index set and if it is, set the next item in a randomElements array (O(M)). Overall you get O(n) + O(nlogn) + O(M), which is worst case O(MlogM).

Sorry for the long-winded comment, hope this makes sense to you :)

Code after:
            byte* input_startptr = input + sizeof(ObjectInputHeader);
            byte* input_currptr = input_startptr;

            int countDone = 0;
            bool isMemory = false;
            MemoryHandle ptrHandle = default;
            byte* ptr = output.SpanByte.ToPointer();

            var curr = ptr;
            var end = curr + output.Length;

            ObjectOutputHeader _output = default;

            try
            {
                int[] indexes = default;

                if (count > 0)
                {
                    // Return an array of distinct elements
                    var countParameter = count > set.Count ? set.Count : count;

                    // The order of fields in the reply is not truly random
                    indexes = Enumerable.Range(0, set.Count).OrderBy(x => Guid.NewGuid()).Take(countParameter).ToArray();

                    // Write the size of the array reply
                    while (!RespWriteUtils.WriteArrayLength(countParameter, ref curr, end))
                        ObjectUtils.ReallocateOutput(ref output, ref isMemory, ref ptr, ref ptrHandle, ref curr, ref end);

                    foreach (var index in indexes)
                    {
                        var element = set.ElementAt(index);
                        while (!RespWriteUtils.WriteBulkString(element, ref curr, end))
                            ObjectUtils.ReallocateOutput(ref output, ref isMemory, ref ptr, ref ptrHandle, ref curr, ref end);
                        countDone++;
                    }
                    countDone += count - countParameter;
                }
                else if (count == int.MinValue) // no count parameter is present
                {
                    // Return a single random element from the set
                    if (set.Count > 0)
                    {
                        int index = RandomNumberGenerator.GetInt32(0, set.Count);
                        var item = set.ElementAt(index);
                        while (!RespWriteUtils.WriteBulkString(item, ref curr, end))
                            ObjectUtils.ReallocateOutput(ref output, ref isMemory, ref ptr, ref ptrHandle, ref curr, ref end);
                    }
                    else
                    {
                        // If set is empty, return nil