Register | Login
Attackpoint - performance and training tools for orienteering athletes

Discussion: Faster Karttapulautin

in: Orienteering; General

Mar 26, 2024 1:01 PM # 
Last year I started to rewrite @Jagge karttapullautin in Rust, a more powerful language than the original perl.

The current iteration of the new software runs about 10 times faster on linux or mac than the original, and about 7 times faster on windows.

I still work to convert all the functions to rust, but the software is already fully usable as it is and it outputs copy conform output files compared to the original script.

You can download the latest version from the Github repo latest release
Mar 26, 2024 2:34 PM # 
Terje Mathisen:
Bravo! I will have to see if this is compatible with the tuned KP version we use for, if anything is missing I should hopefully be able to fix it. (I already use Rust for flattening the up to 10+ LiDAR projects that can cover a single square km tile.)
Mar 26, 2024 3:04 PM # 
good work, highly recommended.
Mar 27, 2024 8:56 AM # 
Terje Mathisen:
I have noticed that the code still seems to use las2txt? I picked up the las-rs Rust library a year or two ago and that's what I use for multi-project LiDAR flattening now.

It is almost an order of magnitude faster than my old code which used lastxt + perl + txt2las.
Mar 27, 2024 9:37 AM # 
I was not aware of the las-rs library.
I definitely could integrate it in the rust code to remove one more dependency, but it is not high priority has it is not a performance bottleneck.

edit: it is now using las-rs
Mar 27, 2024 10:22 AM # 
Mar 27, 2024 8:42 PM # 
Terje Mathisen:
The one issue with las-rs is that it ignores the normal rule about "be flexible in what you accept as input, but strict in what you output". Several Norwegian LiDAR projects breaks one or more of the official rules about what a particular LAS version can or must contain, so I have been using a local fork which defaults to being much more flexible. I have intended from the start to contribute this back to the author, but still haven't found a really clean way to introduce a new "flexible" configuration/macro flag.
Mar 28, 2024 9:04 PM # 
does it still do other functions not listed (sorry I haven't tried it yet):
makevegenew, smoothjoin etc?
Mar 28, 2024 10:48 PM # 
it does all the functions except for a few that are not needed for a map generation, such as groundfix or xyzfixer... in any way it will print an error message if you try to use one of those.
Mar 29, 2024 5:13 PM # 
Terje Mathisen:
Henning Spjelkavik (who runs all the KP-based backend processing for have tested the Rust version and found that it can now process a full 1100x1100m tile (cropped to 1000x1000 after processing to avoid tile edge artifacts) in about 40 sec, and the output seems to be more or less indistinguishable from the original Perl!
This means that we can much more easily afford to reprocess any part of the country which gets an updated scan and/or 3D photo. :-)
Mar 29, 2024 5:58 PM # 
How long did the Perl version take?
Mar 29, 2024 7:24 PM # 
Terje Mathisen:
Nearly an order of magnitude longer afaik.
Mar 29, 2024 7:49 PM # 
Really, really nice. Stunning performance gains, thanks so much!

Building from source in WSL2 worked well. I particularly like that it all stays in one threaded process in batch mode, too.
2548 hughmac 20 0 2981200 2.8g 4436 S 699.7 35.8 19:11.29 rusty-pullauta
Mar 29, 2024 10:45 PM # 
Yes, ~12x speedup for me:
ORIG KP: 24m41.167s
RUST KP: 02m01.747s
Mar 30, 2024 5:59 AM # 
@hughmac4 have you compared the windows build vs the wsl2 one?
Mar 30, 2024 6:55 AM # 
Terje Mathisen:
BTW, triggered by this great news I finally bit the bullet and started to port the PROJ tmerc code from C++ to Perl: Up in Northern Norway the difference between the standard (approx) UTM 33 vs 35 conversion and the "exact" Poder Onsager algorithm is about 10 m!

I found the translation very tedious, but then I did some more github searching and "lo & behold!" proj4rs is now a published crate! :-)

Testing this code last night I got sub-cm offsets between the official Norwegian conversion and the one I got from proj4rs!

It really looks like proj4rs can handle any proj string for the CRS definitions, it was very easy to setup one for UTM33N and another for UTM35N and then simply call transfrom(from, to point3d), with runtime of around half a microsecond/conversion.
Mar 30, 2024 8:03 AM # 
Terje, do you know is there are similar 10m errors if you do such conversion with proj4js? I use it a lot in browser and wonder here if gpx tracks are 10m off up there.
Mar 30, 2024 8:24 AM # 
And l must say I was perplexed when I heard someone got idea of doing such kp rust conversion and even more it actually got finished. I mean, I think there in no way one could understand whats going on there so it must have been quite a task. Must have been like tranlating Sinuhe the Egyptian from Finnish to something like Polish with just dictionary -with the difference of Sinuhe texts actually always making some sense.
Mar 30, 2024 9:04 AM # 
At first being faced with 10K lines of perl in a single file was a bit scary, but the early reward of huge speed improvement kept me going.
Thanks to the division of the map generation in multiple steps it was easy to convert one step at a time.
It wasn't so difficult to translate from one language to another as I didn't have to reinvent the algorithms, just find the right data structures to use... then it is just like a monk doing holy texts transcription...
Mar 30, 2024 1:31 PM # 
@rphlo I had not, having done the WSL2 build just to peek at rust some. But now I have:
>>> WIN = [32.34, 32.14, 32.36, 32.91, 33.51,
33.30, 33.65, 34.63, 35.25, 35.06]
>>> np.mean(WIN)
>>> np.std(WIN)

>>> WSL2 = [19.93, 20.13, 20.17, 20.19, 20.22,
20.29, 20.31, 20.58, 20.58, 20.62]
>>> np.mean(WSL2)
>>> np.std(WSL2)
So the WSL2 build is a good bit faster, but I suspect mostly / solely because of filesystem read / write speeds in the different environments (NTFS WIN, ext4 WSL2) ... if I run the WSL2-built version in the NTFS mount, I get similar speeds to the WIN.

A WSL2 build seems quite "worth it", if you work in the ext4 filesystem, and do a lot of this stuff. BUT! It's so much faster wherever it's used, for general fiddling, it's all great.
Mar 30, 2024 5:35 PM # 
A final set of Windows Laptop tests with another (better?) timing perspective with bigger files. I used a single PA State tile (10k x 10k feet or 9.290304 sq km) 10x each, which I pre-processed solely by converting to UTM 18N / meters and keeping classes 1 & 2 (no thinning, which I normally do):
>>> np.mean(WINinWIN)
>>> np.mean(WSL2inEXT4)
>>> np.mean(WSL2inDEVSHM)
And that's on my weak, old laptop. Using 4x cores, that could (in theory, assuming a whole lot of things) do all of PA (119,280 sq km) in less than 5 days! Crazy.

Not actually sure why the WIN is slower than the WSL2 ... I 'discounted' disk by doing a run in /dev/shm (last one above), and essentially no diff (so no need to use /dev/shm).

Oh! Another tip: if you're using a laptop, make sure it's connected to power. Otherwise performance could be reduced by a lot (~50% in my case) by your power saving features.
Mar 30, 2024 10:35 PM # 
And to close the loop on this, I'm processing Chester, Delaware, Montgomery, and Philadelphia counties in PA (573 tiles, probably a good bit of surrounding counties, as well), using 1x core of my laptop. Will add an overview map and clickable PNG viewing at some point, when some future vacation comes around. So fun!

Basic steps (bash file here):
- pre-create osm directory with all of the OSM data for the entire area (big!!)
- pre-create data.txt file by searching the National Map Viewer, and downloading the txt file (and then filtering for the dataset I want to use, and dos2unix data.txt)

Then in the script, for each tile:
- download the tile from National Map Viewer
- pre-process LAZ (UTM auto, classes 1 & 2, 30% random fraction)
- create a clipped file for the tile (ogr2ogr -spat option)
- rusty-pullauta!
- shape file processing
- clean un-needed things up
- zip and push the temp file to cloud storage
- repeat

Thanks for enabling this insanity, @rphlo! While 5m contours and other KP defaults are likely not perfect for a lot of the tiles, it's a fun start.
Mar 31, 2024 12:19 AM # 
Could we expand that project to NEPA for your next vacation, Hugh?
Mar 31, 2024 2:05 AM # 
Absolutely, @Gswede! I'll ping you when I have some content for you to explore.
Mar 31, 2024 2:41 AM # 
For big areas I would suggest you to use the batch mode. You might find help asking in the github dicussion threads.
People who have processed Spain territory and Sweden are active there. Maybe Terje might want to share some of secret sauce?
Mar 31, 2024 1:54 PM # 
Terje Mathisen:
@jagge: The default/approx UTM formulas work perfectly well within each +/-3 degree zone, as well as pretty OK a bit outside, so for a country like Finland where almost all of this resides within a single zone, using that zone for the entire country is totally unproblematic.
proj4js is not something I have looked carefully into, but I'm pretty sure it is very similar to proj4rs, which means that it either by default use Poder-Onsager everywhere, or like the original C++ PROJ it will use the fast code unless you are both far north and quite some distance offset sideways from the central meridian.
(I don't remember the exact details, but it was something like a simple quadratic formula of northing and easting that exceeded a particular limit.)
Anyway, the proj4rs test code I just ran, converting a million different coordinates near Tana Bridge in Finnmark, from UTM33 to UTM35, took half a microsecond per call and gave results which were identical to the official
Mar 31, 2024 2:11 PM # 
Terje Mathisen:
Here in Norway we are lucky enough to have Henning Spjelkavik who has been running the mapping part of for more than a decade, he generates the docker containers that contain our processing pipeline, and runs them in the background on both local and cloud instances, scaling up as needed.
Our processing is strongly based on 1x1km tiles in UTM33, with a 50m boundary, so that we use 1100x1100m as the actual tile size.
I generate those base tiles by first downloading _all_ modern LiDAR data in Norway, storing it on a Synology NAS with well over 100 TB of raw disk, configured into either RAID5 or mirrored volumes.
Every project is unpacked into /data/-1-xxx-yyy-zz.laz files, and the metadata loaded into a set of MariaDB tables.
When I generate tiles for a new area (or new source data these days) I start by SELECT'ing all the source tiles that fully or partially overlap my target area, then I sort them by priority (mostly date, but also a few other criteria), then I flatten the 2-10 overlapping projects by starting with the top one and marking all the 2x2m cells that contain at least one point. For the secondary projects, any point which lands in an already covered cell is discarded, so I effectively pretend each project to be non-transparent.
I also use more recent 3D photos, where every pixel has a z attribute so that it can be used to locate the current extent of vegetation, typically finding logging that happened after the LiDAR flight.
Mar 31, 2024 3:13 PM # 
I did some converson test with Tana Bridge and saw 100m error, but then after some cursing I realized there is no error, the bridge is rather new and rebuild in an other place than the old one I was comparing to...
Mar 31, 2024 5:59 PM # 
Terje Mathisen:
@jagge: Moving bridges for the win! :-)
Apr 3, 2024 7:03 AM # 
I published yesterday the last missing step, the shapefile renderer in rust, in a release candidate version.
This means there is no perl code used anywhere anymore and that the rust code is self sufficient.
I also updated the doc to reflect this.

I invite everybody to test it and report any issue or success, particularly the with the vectorconf settings. If report shows it works as expected I could publish this as an official release in a week or so.
Apr 4, 2024 5:19 AM # 
Terje Mathisen:
@rphlo: This (shp support) is really appreciated! We can't use this directly here in Norway/ since all our national topo data use SOSI, a unique/national ascii based file format, but there are both commercial and open source projects to convert SOSI into Shape.

For my own base map generation, I wrote a converter since dxf is supported by both OCAD and OOM, and SOSI and DXF are similar in that they are fairly verbose ascii-based file formats, so relatively easy to parse/understand/debug.

The trickiest parts are probably related to where I have to make orienteering judgments about combinations of SOSI symbols, i.e. like how to omit black river boundaries on creeks that are just 1 or two meters wide, or suppressing underground objects like a creek going into a culvert, or a road passing through a tunnel.

For sprint maps with grey buildings I have also considered trying to suppress all building-internal boundary lines, i.e. like roofs split into multiple panels.

Anyway, like you I do like the "Rewrite it in Rust" (RiiR) meme, but don't see the need to do so for sosi2dxf because the processing needed is not really speed critical, and it fits very nicely into Perl's main area of expertise.
Apr 4, 2024 7:00 AM # 
I downloaded and run it from command line, got strange errors during shape rendering step when processing a folder of laz files and shp zips in batch mode. Then I tried the previous (stable) version and it worked fine. Then I tried the latest again in non batch mode and it was fine. Then in batch mode with an other dataset and now I can't get it fail again. I think/hope it was just some kind of security issue, a security feature not letting it run properly at first, but after some double clicking it and telling it to take the very very high risk of executing rphlo's app it was fine. But not entirely sure because I accidentally deleted the original folder and input files I got errors with. I guess what I am trying to say here is I am testing this but apparenly not as systematic way as I should.
Apr 4, 2024 8:21 AM # 
@jagge I pushed a new version that fixed some bug with shape files since your last message...
Apr 5, 2024 12:08 AM # 
I'm not much of a KP or Rust expert. But have had a play the last two days on windows with WSL and on an HPC platform with Milan cpus and having everything inside rust has been really easy to get setup and use and blazing fast.

very much appreciate, thank you.

if anyone wants to share a set of batch commands etc, I have 60,000 cpus to play with :D

Please login to add a message.