Index
> Projects and Ideas > Is that algorythm fastest & workable? |
| Author |
|
|
bitRAKE 07 May 2021, 03:13
Code: .searchloop: push ecx mov ecx, edx push edx push edi push esi repz cmpsb pop esi pop edi pop edx pop ecx jz found repnz scasb jz .searchloop .notfound: pop eax push ecx _________________ ¯\(°_o)/¯ “languages are not safe - uses can be” Bjarne Stroustrup |
|||
07 May 2021, 03:13 |
|
|
revolution 07 May 2021, 03:16
Do you mean the "fastest" implementation, or the fastest algorithm? You ask for an algorithm but present an implementation.
Algorithms and their implementations are very different things. And their relative performances are only vaguely linked to each other. One is measured by seconds, the other with the big-O notation. Finding the fastest big-O value is easy. There are about a billion papers and studies published regarding searching for substrings. Finding the "fastest" general implementation is almost impossible. The sheer number of combinations makes it intractable. |
|||
|
07 May 2021, 03:16 |
|
|
ProMiNick 07 May 2021, 06:27
Code: .searchloop: ; bitRAKE, I`m understand what thou mean - preserving edx is useless, just preserve ecx push ecx mov ecx, edx push edi push esi repe cmpsb pop esi pop edi pop ecx je .found repne scasb je .searchloop .notfound: pop ecx push ecx vs pop ecx push ecx - 2 bytes - 2 tacts I guess it is case of preference. I prefer to ensure that in top of stack & ecx would be same value by reading it, pop-push looks less readable. |
|||
|
07 May 2021, 06:27 |
|
|
bitRAKE 07 May 2021, 07:10
I'm more apt to use flag value return for such a leaf. It might cost an extra instruction, but it save an instruction every use.
Code: call MemoryPos jnz not_found Code: call MemoryPos inc eax jz not_found _________________ ¯\(°_o)/¯ “languages are not safe - uses can be” Bjarne Stroustrup |
|||
|
07 May 2021, 07:10 |
|
|
Roman 07 May 2021, 08:07
Quote:
This code bad if we want 64 bit program. My solution: Code: .searchloop: ; bitRAKE, I`m understand what thou mean - preserving edx is useless, just preserve ecx movd xmm0,ecx mov ecx, edx movd xmm1,edi movd xmm2,esi repe cmpsb movd edi,xmm1 movd esi,xmm2 movd ecx,xmm0 je .found repne scasb je .searchloop .notfound: movd ecx,xmm0 |
|||
|
07 May 2021, 08:07 |
|
|
bitRAKE 07 May 2021, 08:34
The 64-bit version is a couple bytes larger, but fine otherwise.
Code: GetStrLength: ; string: [in] rdi ; string length: [out] ecx ; [unchanged] rbx, rdx, rsi, rdi, rbp, rsp or ecx, -1 xor eax, eax repnz scasb not ecx sub rdi,rcx retn ;----------------------------------------------------------------------- MemoryPos: ; memory: [in] rsi ; pattern: [in] rdi ; memorysize: [in] rdx ; patternpos: [out] eax , -1 mean notfound ; [unchanged] rbp, rsp call GetStrLength xchg edx, ecx xchg rdi, rsi MemoryBlockPos: ; memory: [in] rdi ; pattern: [in] rsi ; memorysize: [in] ecx ; patternsize: [in] edx ; patternpos: [out] eax , -1 mean notfound ; [unchanged] rbp, rsp lodsb push rcx repnz scasb jnz .notfound dec edx jz .found .searchloop: push rcx mov ecx, edx push rdi push rsi repz cmpsb pop rsi pop rdi pop rcx jz found repnz scasb jz .searchloop .notfound: pop rax push rcx .found: pop rax sub eax, ecx dec eax retn ; P.S. 72 chars are opimal to fit in one line for printing code for ex.- ; It is one ";" and 71 "-" --------------------------------------------- ; at A4 list 80x56 of CourrierNew size 9 will fit 56 lines ------------- ; with left border = 3 sm (6 chars) and right one = 1 sm (2 chars) ----- _________________ ¯\(°_o)/¯ “languages are not safe - uses can be” Bjarne Stroustrup |
|||
|
07 May 2021, 08:34 |
|
|
DimonSoft 07 May 2021, 10:48
ProMiNick wrote: mov ecx, [esp] - 3 bytes - 1 tact I guess, this needs a reference to the source of the information and detailed analysis of its applicability to modern processor models with all the hardware optimizations involved that make equations of “instruction = N ticks” type… obsolete? |
|||
|
07 May 2021, 10:48 |
|
< Last Thread | Next Thread > |
Forum Rules:
|