On 12/03/15 18:03, Carsey, Jaben wrote:
> Shumin,
>
> Could we loop over a list of handles made by
> 1) LocateHandleBuffer on BlockIO
> 2) LocateHandleBuffer on SimpleFileSystem
> 3) Combine these lists (removing duplicates)
So this is exactly the use case that I had in mind (regardless of this
patch -- sorry again for hijacking the thread).
First, LocateHandleBuffer() with ByProtocol could be sped up if the
system maintained an "index by protocol GUID".
Second, combining two result sets (while removing or pinpointing
duplicates) is something I had to optimize occasionally in a previous
life (yes, I coded PL/SQL :)). Off the top of my head, I recall three
join methods that Oracle's execution plan generator used: hashing, sort
& merge, and nested loops.
If I recall correctly, in edk2 many joins are implemented with nested
loops (where the inner lookup is linear: O(n), resulting in O(n^2) time
for the join). I wonder if we could put the red-black tree library to
use somewhere (which rould result in O(logn) inner lookup time). Of
course the actual values of "n", and the constants inherent in that
library could defeat the whole idea.
So, as a first step, it would be nice to profile some shell commands,
and find the hot spots. Does edk2 support profiling in any form?
(Just musing...)
Thanks
Laszlo
>
> Would that be faster? Not sure if this would be worth it, but something I
> thought of... Your change is still good.
>
> Reviewed-by: Jaben Carsey <jaben.car...@intel.com>
>
>> -----Original Message-----
>> From: Qiu, Shumin
>> Sent: Wednesday, December 02, 2015 9:36 PM
>> To: edk2-devel@lists.01.org
>> Cc: Qiu, Shumin <shumin....@intel.com>; Carsey, Jaben
>> <jaben.car...@intel.com>
>> Subject: [PATCH] ShellPkg: Refine the code to reduce time cost of 'map -r'
>> Importance: High
>>
>> In some platform 'map -r' may cost more than 1 min. This patch filter the
>> target handles by
>> BlockIO and SimpleFileSystem protocol to reduce the time cost.
>>
>> Cc: Jaben Carsey <jaben.car...@intel.com>
>> Contributed-under: TianoCore Contribution Agreement 1.0
>> Signed-off-by: Qiu Shumin <shumin....@intel.com>
>> ---
>> .../Library/UefiShellCommandLib/ConsistMapping.c | 40
>> ++++++++++++++++------
>> 1 file changed, 30 insertions(+), 10 deletions(-)
>>
>> diff --git a/ShellPkg/Library/UefiShellCommandLib/ConsistMapping.c
>> b/ShellPkg/Library/UefiShellCommandLib/ConsistMapping.c
>> index 9bd7b2c..86e8dc5 100644
>> --- a/ShellPkg/Library/UefiShellCommandLib/ConsistMapping.c
>> +++ b/ShellPkg/Library/UefiShellCommandLib/ConsistMapping.c
>> @@ -16,6 +16,10 @@
>> #include <Library/SortLib.h>
>> #include <Library/UefiLib.h>
>> #include <Protocol/UsbIo.h>
>> +#include <Protocol/BlockIo.h>
>> +#include <Protocol/SimpleFileSystem.h>
>> +
>> +
>>
>> typedef enum {
>> MTDTypeUnknown,
>> @@ -1349,20 +1353,22 @@ ShellCommandConsistMappingInitialize (
>> OUT EFI_DEVICE_PATH_PROTOCOL ***Table
>> )
>> {
>> - EFI_HANDLE *HandleBuffer;
>> - UINTN HandleNum;
>> - UINTN HandleLoop;
>> - EFI_DEVICE_PATH_PROTOCOL **TempTable;
>> - EFI_DEVICE_PATH_PROTOCOL *DevicePath;
>> - EFI_DEVICE_PATH_PROTOCOL *HIDevicePath;
>> - UINTN Index;
>> - EFI_STATUS Status;
>> + EFI_HANDLE *HandleBuffer;
>> + UINTN HandleNum;
>> + UINTN HandleLoop;
>> + EFI_DEVICE_PATH_PROTOCOL **TempTable;
>> + EFI_DEVICE_PATH_PROTOCOL *DevicePath;
>> + EFI_DEVICE_PATH_PROTOCOL *HIDevicePath;
>> + EFI_BLOCK_IO_PROTOCOL *BlockIo;
>> + EFI_SIMPLE_FILE_SYSTEM_PROTOCOL *SimpleFileSystem;
>> + UINTN Index;
>> + EFI_STATUS Status;
>>
>> HandleBuffer = NULL;
>>
>> Status = gBS->LocateHandleBuffer (
>> - AllHandles,
>> - NULL,
>> + ByProtocol,
>> + &gEfiDevicePathProtocolGuid,
>> NULL,
>> &HandleNum,
>> &HandleBuffer
>> @@ -1385,6 +1391,20 @@ ShellCommandConsistMappingInitialize (
>> continue;
>> }
>>
>> + Status = gBS->HandleProtocol( HandleBuffer[HandleLoop],
>> + &gEfiBlockIoProtocolGuid,
>> + (VOID **)&BlockIo
>> + );
>> + if (EFI_ERROR(Status)) {
>> + Status = gBS->HandleProtocol( HandleBuffer[HandleLoop],
>> + &gEfiSimpleFileSystemProtocolGuid,
>> + (VOID **)&SimpleFileSystem
>> + );
>> + if (EFI_ERROR(Status)) {
>> + continue;
>> + }
>> + }
>> +
>> for (Index = 0; TempTable[Index] != NULL; Index++) {
>> if (DevicePathCompare (&TempTable[Index], &HIDevicePath) == 0) {
>> FreePool (HIDevicePath);
>> --
>> 1.9.5.msysgit.1
>
> _______________________________________________
> edk2-devel mailing list
> edk2-devel@lists.01.org
> https://lists.01.org/mailman/listinfo/edk2-devel
>
_______________________________________________
edk2-devel mailing list
edk2-devel@lists.01.org
https://lists.01.org/mailman/listinfo/edk2-devel
