Page MenuHomePhabricator
Create Task
Maniphest T1224

Pawsort Optimizations
Open, p2: LaterPublic4 Energy Points (d+f*r)
Actions

Description

Benchmark data as of D240: Fix PawSort (intro_sort and heap_sort):

TestResult (Baby Bear, Adjusted)
P-tB3001: Sorted ArrayWon (+220495 cycles)
P-tB3002: Reversed ArrayLost (-118451 cycles)
P-tB3003: Nearly, Invert 2Lost (-66325 cycles)
P-tB3004: Nearly, Invert 5Lost (-155802 cycles)
P-tB3005: Few UniqueLost (-735967 cycles)
P-tB3006: Black SheepLost (-72129 cycles)
P-tB3007: Double ClimbWon (+63023 cycles)
P-tB3008: Double DropWon (+564468 cycles)
P-tB3009: StairsWon (+285690 cycles)
P-tB3010: MountainWon (+501040 cycles)
P-tB3011: Double MountainLost (-197263 cycles)
P-tB3012: EverestWon (+381001 cycles)
P-tB3013: CliffWon (+648601 cycles)
P-tB3014: SpikeWon (+454654 cycles)
P-tB3015: CliffWon (+699406 cycles)
P-tB3016: NightmareLost (-1056965 cycles)

Details

Task Type
Improvement
Proposed Urgency
Established
Gravity
g4: Significant
Friction
f3: Off-Road
Relativity
r2: Low
Volatility (Caught At)
Not a Bug
Origin
Not a Bug/Unknown

Related Objects
Search...

StatusAssignedTask
 Completedlulu731T758 Introsort
 Openlulu731T1224 Pawsort Optimizations

Event Timeline

jcmcdonald triaged this task as p1: Eventual priority.Sep 12 2018, 1:15 PM
jcmcdonald created this task.
jcmcdonald added a comment.Sep 12 2018, 1:20 PM

One possible optimization would be to change swap(...) to a macro, which will reduce instruction cache misses.

I'd also recommend hand-checking some of the problem scenarios (on paper). This might help show where the algorithm and/or implementation is inefficient.

Third, I've had good experiences using Callgrind (part of Valgrind), combined with KCacheGrind. This will show what functions are taking up the largest percentage of the CPU cycles.

jcmcdonald updated the task description. (Show Details)Sep 12 2018, 1:21 PM
jcmcdonald added a subscriber: iaroslavski.EditedSep 14 2018, 6:52 AM

From chat...

<@iaroslavski> you're using a lot "swap" methods. Please look at my implementation of DPQ and insertion sort: there are no any swap method! Swap uses 3 assignments, we can use "swap" in theoretical algorithms to have clear understanding, but real implementation should not have such expensive methods, only regular assign.

<@jcmcdonald> Would it be reasonable to use a macro in that capacity, for reasonably DRY code?

<@iaroslavski> No, macro will help a bit: no invocation of method, but the number of assignments will be the same: 3, You should change logic of sorting.

jcmcdonald raised the priority of this task from p1: Eventual to p2: Later.Sep 14 2018, 7:25 AM
jcmcdonald changed Gravity from Triage Gravity to g4: Significant.
jcmcdonald changed Relativity from Triage Relativity to r2: Low.
jcmcdonald changed Friction from Triage Friction to f3: Off-Road.
lulu731 added a comment.EditedSep 26 2018, 1:24 PM

Benchmark data : (all results are Baby Bear, Adjusted)

TestBefore iterators implWith iteratorsIterators + XOR SWAPIncreasing Tiny_size
P-tB3001: Sorted ArrayWon (+389975 cycles)Won (+375676 cycles)Won (+376778 cycles)Won (+214292 cycles)
P-tB3002: Reversed ArrayLost (-201692 cycles)Lost (-176235 cycles)Lost (-199608 cycles)Won (+25186 cycles)
P-tB3003: Nearly, Invert 2Lost (-127672 cycles)Lost (-90659 cycles)Lost (-135010 cycles)Won (+181679 cycles)
P-tB3004: Nearly, Invert 5Lost (-131854 cycles)Lost (-97407 cycles)Lost (-176462 cycles)Won (+139774 cycles)
P-tB3005: Few UniqueLost (-1099142 cycles)Lost (-1103158 cycles)Lost (-1177709 cycles)Lost (-875622 cycles)
P-tB3006: Black SheepLost (-25109 cycles)Lost (-18475 cycles)Lost (-37758 cycles)Won (+215353 cycles)
P-tB3007: Double ClimbRoughly identicalWon (+58692 cycles)Lost (-74685 cycles)Won (+110325 cycles)
P-tB3008: Double DropWon (+357471 cycles)Won (+445612 cycles)Won (+323542 cycles)Roughly identical
P-tB3009: StairsWon (+89961 cycles)Won (+150866 cycles)Won (+18197 cycles)Won (+206022 cycles)
P-tB3010: MountainWon (+250665 cycles)Won (+337091 cycles)Won (+240322 cycles)Won (+222330 cycles)
P-tB3011: Double MountainLost (-253465 cycles)Lost (-172114 cycles)Lost (-316822 cycles)Lost (-143572 cycles)
P-tB3012: EverestWon (+251219 cycles)Won (+333247 cycles)Won (+235931 cycles)Won (+230587 cycles)
P-tB3013: CliffWon (+550778 cycles)Won (+589778 cycles)Won (+505695 cycles)Won (+693633 cycles)
P-tB3014: SpikeWon (+254366 cycles)Won (+336193 cycles)Won (+235545 cycles)Won (+230636 cycles)
P-tB3015: ChickenLost (-70111 cycles)Lost (-19491 cycles)Lost (-75024 cycles)Won (+76022 cycles)
P-tB3016: NightmareLost (-1467850 cycles)Lost (-1490940 cycles)Lost (-1571186 cycles)Lost (-1477948 cycles)
jcmcdonald edited projects, added PawLIB [Project]; removed PawLIB [Project] (2.1), Unknown Object (Project).Jan 23 2020, 1:55 PM
jcmcdonald moved this task from Backlog to 2.3 on the PawLIB [Project] board.Apr 13 2020, 5:17 PM
jcmcdonald edited projects, added PawLIB [Project] (2.3); removed PawLIB [Project].
Copyright (C) 2019 MousePaw Media. All Rights Reserved. · Community Rules · Terms of Use · Privacy Policy · Terms of Development