Member Avatar for TomCo

Hi, I’m doing a little project at the moment that’s centred around the optimisation of insertion sort.

I removed the various stalls when possible, made various modifications and unrolled some loops. I got it down to about 14927 Cycles with a CPI of 1.007 when sorting 100 elements. Is this reasonable for Insertion sort?

Could someone share the code for Quick Sort so I can compare the two myself?

  • 2 Contributors
  • 2 Replies
  • 392 Views
  • 2 Days Discussion Span
  • Latest Post Latest Post by TomCo
Member Avatar for MipsMan

yea sure, post your insertion sort mips code, and i'll see what i can recommend for you!

quicksort is a better search algorithm in general, but its a lot, lot harder to do in mips.

Member Avatar for TomCo 
.data
array: .word 0x18D5923817B8180, 0x74D704382FE3F78, 0xBEE15CB67F5BAA0,0xE6E2E34C050051F, 0x6E1C1F82F4B2EB6, 0xC0C9FE47229D755
      .word 0x0CC8A, 0x6A8CF0DBB711124, 0xF23B1E513BA8462,0x63CAB5A5839CA2F, 0x54B062, 0xBE05403895A748F
      .word 0x66D9B81F, 0xA4B2BDA838C0D2D, 0x2EC2E1A569F7C4A,0x8490F, 0x1B8E20907814780, 0xB86114
      .word 0xF0765CEA8A, 0xE72BD3120140290, 0xFCFBEAD,0x6A3862C366CAC05, 0x3CCA9025C86D9DE, 0xEC75090C22A4519
      .word 0x398FBEB462DD0, 0xEDBA4FB12CF45A6, 0xEF,0xC7F7C3C222CB5CE, 0xF923E9D334EF46B, 0x9B0C81B
      .word 0x3C7CE6319849F86, 0xFAC8EB1DF825CB1, 0x05A644,0x6E5743A19A10CE, 0x75EE2972ED8C307, 0xF4B
      .word 0x434B0CB3B3132F6, 0xF71DBF8EDEB5EC6, 0xFBE2D732C9041B,0xFA732A2AB1196CC, 0xC8D11904, 0x1D738614C93367A
      .word 0xB424E1DC4, 0x6703DB4172D0AEF, 0x438892B9,0xC6CE5FABBE0CDC9, 0xEF52F4AEC0128F5, 0xF078FC74
      .word 0x774A243C3AC09, 0x5C48B2242B57EAC, 0x4B0C325,0x4209EC875AC42F2, 0x4399F55E37, 0x852520032BA0AC8
      .word 0x1D88F0662C, 0x9D41DF101814DF6, 0x81809478FF7DDF8,0x38DD3BEC2, 0x297040, 0xD98D14D9788B2D4
      .word 0xF58F2B6C, 0x6FB738A9099, 0x2D2862DA15A5325,0xB5901FD9F9786A5, 0xAD4B4DF7C8CD016, 0xC9E47931EC9DE5C
      .word 0xB963A, 0x562F6469AD79E3B, 0x86C07A669D2C92A, 0xE345426,0x695DA7A33540BA6, 0x57854818ED920E8
      .word 0x2B6, 0x8EC736BE5D3816A, 0x726B8C27925DAF7, 0x48BE008,0x988CF0CB7957F87, 0xC3AA706611AA16F
      .word 0x8, 0xBF819B5CC55B42B, 0x3AD5FE591266AA4, 0x998D,0x7EF41415BB7CE5, 0x169252F1E172ADD
      .word 0x8F5D8B5D, 0xA893FE08A0FBC6D, 0x6718E483A6221FC,0x32474F9CCAE6C01, 0x0xB7E51D74F45DD26
      .word 0x863A273C8794, 0xF205EF8BC, 0x843BA4132FAC41,0x6CDD9050FA348C0, 0x0F11E9, 0x6ABB0B8C399BF26
      .word 0x3896D, 0xD651B78E6A6C008, 0xA321741, 0x511B12B27

len:    .word 100

        .text
	ld r2,len(r0)    ; r2 = len
        dadd r1,r0,r0    ; r1 = i = 0
        dsll r2,r2,3     ; r2=k*8
        slt r3,r1,r2	 ; for.....
	dadd r6,r0,r1    ; j=i
        beqz r3,out
        ld r4,array(r1)  ; r4=B			
	daddi r7,r6,-8	 ;loop......
        ld r5,array(r7)
	sd r5,array(r6)
        slt r3,r4,r5
	sd r5,array(r6)
	dadd r10,r0,r7		
	movn r10,r6,r3	 ;got rid of that branch
over:   sd r4,array(r6)  ; a[j] = B
	daddi r1,r1,8    ; i++
for:    slt r3,r1,r2
	dadd r6,r0,r1    ; j=i
        beqz r3,out
        ld r4,array(r1)  ; r4=B
loop:	daddi r7,r6,-8
        ld r5,array(r7)
	sd r5,array(r6)
        slt r3,r4,r5
	sd r5,array(r6)
        beqz r3,over
        dadd r6,r0,r7

[B]code after the loop label repeated 32 times.[/B]

	j loop

out:    halt

There you go!

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.