SBASIC & C++

Anything QL Software or Programming Related.
stevepoole
Super Gold Card
Posts: 712
Joined: Mon Nov 24, 2014 2:03 pm

Re: SBASIC & C++

Post by stevepoole »

Hi,
Yes there are plenty of benchmarks around, but most for programs written in C or C++. Same thing for test data. So of limited value for comparing to superbasic TSP.
The program printed in Quanta, contains a flag to use test data of french cities, so that is how I know the accuracy.
The reference travelling salesman program is called 'Concorde', and there are plenty of benchmarks for it on the web. The Quanta 'Shrink' tsp seems to be better, at least up to 800 cities, and I suspect when optimised could be Ok for tens of thousands, but at present I can't yet see how to eliminate redundant calculations without bloating the stack.
This is where anybody who can see a way of improving the program would be welcome.
Don't forget, the TSP is one of the six 'Millenium problems' which have yet to be solved.
Shrink may do just that ...but we won't know until it has been evaluated by Professional mathematicians, and I am having great difficulty in contacting any such person.
Thanks for your comments. All help is appreciated.
Steve.


EmmBee
Trump Card
Posts: 240
Joined: Fri Jan 13, 2012 5:29 pm
Location: Kent

Re: SBASIC & C++

Post by EmmBee »

Hi folks,

I’ve been working with Steve for a few months now on the TSP program.

Much has been achieved in this time. Values are stored in arrays, rather than keep computing them again each time around the loop. A new way of storing the nodes has been found – that is they are not stored anywhere! Instead, there are two pointer arrays, “nex()” and “prev()” which tells where each node is connected to. The program is now, or should be, very easy to understand. For anyone wishing to try some algorithms out, this could be the ideal program to try it on.

“Shrink” first constructs a tour, and then proceeds to improve on existing links to try to form a shorter tour. The improvement strategy employed is of a very simple nature, but is evidently fairly useful. On test data of 36 French cities, the optimal distance is found, which we are quite pleased with. More powerful improvement techniques are needed if we are to progress . We would welcome any help, and particularly if you can supply actual SBASIC code. We are trying to make this a useful program and have great ambitions for it. I am sure we will get somewhere; it could be just a matter of time.

There is a trace mode, which is toggled on/off with Shift_Spacebar. With trace mode on, the spacebar can be tapped to single step through solutions. It can be quite fascinating to watch how “shrink” carries out its work on the test data, and after replacing various links, eventually finds the optimum solution.

If you would like a copy of Shrink, then PM me your email address, and I will send you the latest version.

Kind regards,

Michael
EmmBee


stevepoole
Super Gold Card
Posts: 712
Joined: Mon Nov 24, 2014 2:03 pm

Re: SBASIC & C++

Post by stevepoole »

Hi All,
As EmmBee so rightly states, he has considerably accelerated the 'shrink' Travelling Salesman Program, the prototype version of which was printed in Quanta magazine.. We have got to the point where further optimisations will demand some very clever tricks. Indeed, the time has come where future progress may lie in converting the program to the 'C' language to get that much extra speed.
But in the meantime, if anyone can convert test data written in 'C' to superbasic, that would be a good starting point. There is a lot of test data available, most of it is gzip'ed. We need big test data to run the program on QPC2 with thousands of nodes. If we can get 'shrink' to operate efficiently with such data, we will have acheived our goal...to compete with the 'Concorde' TSP. We are getting very close, the program giving good results with VLSI drilling circuits, and national city tours.
The whole TSP problem is still a subject of important research by mathematicians worldwide, and we hope to get 'shrink' published in a peer-reviewed journal ASAP.
If you think you can help, or are just interested, please get in touch.
best wishes,
Steve Poole.


stevepoole
Super Gold Card
Posts: 712
Joined: Mon Nov 24, 2014 2:03 pm

Re: SBASIC & C++

Post by stevepoole »

Hi Folks,
I have found a TSP expert who will transpose the Travelling Salesman Program into C++. But this could take quite some time, as he is a very overworked person at the moment. In the meantime I am learning C++ myself, but this is a long-winded experience. In the last Quanta magazine, there was printed a very short 'Tally_sort' routine, and It would be interesting to see the speed a C++ version would take, as this would give an indication of the expected acceleration that the TSP could achieve.
If anyone would care to transpose Tally_sort into C++ for us, this would be very helpful, as it might take me a long time before I master C++ sufficiently. For a C++ programmer, this should be a trivial task.
For those interested, benchmarking superbasic reveals that assignments are very slow. This is because of coercion and range checking, which C++ code can shunt. So it is a very fast language, if code is properly written.
The purpose of all this is because most TSP programs are written in C or C++, and we need to compare our 'shrink' program to them. EmmBee, Thomas and I would be very grateful for any such cooperation.
Regards,
Steve.


stevepoole
Super Gold Card
Posts: 712
Joined: Mon Nov 24, 2014 2:03 pm

Re: SBASIC & C++

Post by stevepoole »

Hi All,
The 'Shrink' Travelling Salesman' programming project has been joined by John Powell, who has transcoded a superbasic tally_sort into 'C'. The resulting progam runs 250 times faster, which bodes well for the TSP once transcoding will have been completed.
The superbasic was first rewritten by John to make it C-like. The C-like program was Turbo-compiled, but only ran 4.5 times faster than SB.
Many years ago, Bruno Coativy rewrote 'tally_sort' in assembler, 240 times faster than SB.
This reveals that 'C' or 'C++' compiler-compatible code is verbose, but much faster than turbo-compiled SB.
Our next task is to transcode 'shrink' into 'C', a much bigger task which could take several months, but we have an expert C++ programmer to advise us. He is also a TSP specialist, and has already suggested an optimisation for shrink.
Once shrink exists in Compiled C++, we will know just how well it performs, compared to existing TSP programs which are written either in C or C++.
The learning curve for C++ is steep, but once code has been developped and finalised in SB, then rewritten to be C-like, the effort is no doubt worthwhile. But C68 and Cport are of little help.
Any suggestions would be greatly appreciated.
Steve.


stevepoole
Super Gold Card
Posts: 712
Joined: Mon Nov 24, 2014 2:03 pm

Re: SBASIC & C++

Post by stevepoole »

Hi,
John has now rewritten the tally_sort_bas program slightly differently to make it compatible with different cross-compilers. So now C68 produces executable code. The code execs well on QPC2 and natively on a PC system, but not on QEmulator...
Once work on the tally program will have revealed exactly how to write Cee-like basic, we will be ready to transcode the 'shrink' TSP itself, a much bigger task. But when the TSP will be in C68 'C', it will be a fairly simple task to optimise it for even faster C++ compilation.
As can be seen, it is still easier to develop 'C-like' superbasic programs than to write and debug C code itself... So QL Forever!
Best wishes,
Steve.


stevepoole
Super Gold Card
Posts: 712
Joined: Mon Nov 24, 2014 2:03 pm

Re: SBASIC & C++

Post by stevepoole »

Hi,
Thanks to John, the TSP team now have a common C68 programming interfeace up and running. So we can produce code executable on QPC2 and native PCs. This was not straightforward to implement on modern laptops with earlier versions of QPC2, but the job is now done.

Since we now have the Tally_bas sort routine converted, tested and timed, we are looking to transcode the much larger 'shrink' TSP program. Does anyone have any experience with CPORT or any other QL program to port SuperBasic code into 'C' ? If so, could you please let us have your advice on how to obtain it and what limitations it might have...

Writing 'SB' in 'C' is not too troublesome, provided the basic is well written, and you only use standard C, without the bells and whistles... It is just the syntax which is different. So our next task is to ensure our SB is C-like.

Steve.


stevepoole
Super Gold Card
Posts: 712
Joined: Mon Nov 24, 2014 2:03 pm

Re: SBASIC & C++

Post by stevepoole »

Hi again,
On re-reading all the previous postings on this subject, I see that Van Peebles has CPORT.
The TSP team would like to obtain a copy, if this is permissable...
Steve.


stevepoole
Super Gold Card
Posts: 712
Joined: Mon Nov 24, 2014 2:03 pm

Re: SBASIC & C++

Post by stevepoole »

Hi,
Thanks to John Powell, the Tally sort demonstration program has now been converted to 'C' code. This I then transcoded into C++. The result is that the C++ code runs 500 times faster than the SuperBasic code.
The source code is but 2ko, but the .exe ways in at over 1 mega!
With this sort of acceleration, we are now quite optimistic for the future of the 'Shrink' Travelling Salesman Program. Work is in progress.
Happy New Year!
Steve.


stevepoole
Super Gold Card
Posts: 712
Joined: Mon Nov 24, 2014 2:03 pm

Re: SBASIC & C++

Post by stevepoole »

Hi,
The superbasic tally_sort has now been coded in C++, using floating point arrays with pointers. It is twice as slow as using integer arrays, but some 250 times faster than Superbasic all the same!
This finaly replies to my first posting on the forum dated 24 nov 2014...
So now EmmBee has rewritten an integer version of the 'shrink' TSP in a form suitable for transcoding by CPORT & CFIX for C68. John Powell will supervise the Cporting and I will convert the C68 'C' source into C++, which is a faster implementation of 'C'. Using C68, CPort and Cfix has been troublesome, since they were written in 1992, and we now have emulators, so quirks have appeared which required special treatments. (These programs were designed to run from floppies). Luckily you can buy USB floppies cheaply.
It will be interesting to see just how fast the C++ Travelling Salesman program runs... then we can compare it to existing TSPs on the net. It is not yet clear how S*B graphics will transcode to PC ones...
In the meantime, we shall be adapting some standard C++ routines into S*B to improve our 'shrink' performance. So SuperBasic is a great prototyping tool, but we need C++ transcoding to link to the world of modern PCs, or rest forever up a side-street!
Ql Forever...
Steve.


Post Reply